Embedding spanning subgraphs in uniformly dense and inseparable graphs. Issue 4 (24th August 2020)

• Record Type: Journal Article
• Authors: Ebsen, Oliver; Maesaka, Giulia S.; Reiher, Christian; Schacht, Mathias; Schülke, Bjarne
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 1077
• Page End: 1096
• Publication Date: 2020-08-24
• Subjects: absorption method -- bandwidth theorem -- powers of Hamiltonian cycles; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20957
• Languages: English
• ISSNs: 1042-9832

Abstract

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