MATH Seminar

Title: Spanning subgraphs in uniformly dense and inseparable graphs
Seminar: Combinatorics
Speaker: Mathias Schacht of The University of Hamburg and Yale University
Contact: Dwight Duffus, dwightduffus@emory.edu
Date: 2019-09-06 at 4:00PM
Venue: MSC W301
Download Flyer
Abstract: We consider sufficient conditions for the existence of k-th powers of Hamiltonian cycles in n-vertex graphs G with minimum degree cn for arbitrarily small c >0 . About 20 years ago Komlós, Sarközy, and Szemerédi resolved the conjectures of Pósa and Seymour and obtained optimal minimum degree conditions for this problem by showing that c=k/k+1 suffices for large n. For smaller values of c the given graph G must satisfy additional assumptions. We show that inducing subgraphs of density d>0 on linear subsets of vertices and being inseparable, in the sense that every cut has density at least c, are sufficient assumptions for this problem and, in fact, for a variant of the bandwidth theorem. This generalises recent results of Staden and Treglown.