Embedding spanning subgraphs in uniformly dense and inseparable graphs

Abstract

We consider sufficient conditions for the existence of $k$-th powers of Hamiltonian cycles in $n$-vertex graphs $G$ with minimum degree $\mu n$ for arbitrarily small $\mu >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 $\mu =\frac{k}{k+1}$ suffices for large $n$. For smaller values of $\mu$ 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 $\mu >0$, are sufficient assumptions for this problem and, in fact, for a variant of the bandwidth theorem. This generalises recent results of Staden and Treglown.