Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs. Issue 1 (17th July 2018)

• Record Type: Journal Article
• Authors: Nenadov, Rajko; Škorić, Nemanja
• Is Part Of: Random structures & algorithms. Volume 54:Issue 1(2019)
• Page Start: 187
• Page End: 208
• Publication Date: 2018-07-17
• Subjects: absorbing method -- Hamilton cycles -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20782
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: We show that for every k ∈ N there exists C > 0 such that if p k ≥ C log 8 n / n then asymptotically almost surely the random graph G ( n, p ) contains the k th power of a Hamilton cycle. This determines the threshold for appearance of the square of a Hamilton cycle up to the logarithmic factor, improving a result of Kühn and Osthus. Moreover, our proof provides a randomized quasi‐polynomial algorithm for finding such powers of cycles. Using similar ideas, we also give a randomized quasi‐polynomial algorithm for finding a tight Hamilton cycle in the random k ‐uniform hypergraph G ( k ) ( n, p ) for p ≥ C log 8 n / n . The proofs are based on the absorbing method and follow the strategy of Kühn and Osthus, and Allen et al. The new ingredient is a general Connecting Lemma which allows us to connect tuples of vertices using arbitrary structures at a nearly optimal value of p . Both the Connecting Lemma and its proof, which is based on Janson's inequality and a greedy embedding strategy, might be of independent interest.