|Title: Spanning subgraphs in uniformly dense and inseparable graphs|
|Speaker: Mathias Schacht of The University of Hamburg and Yale University|
|Contact: Dwight Duffus, firstname.lastname@example.org|
|Date: 2019-09-06 at 4:00PM|
|Venue: MSC W301|
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.
See All Seminars