Premium
Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
Author(s) -
Nenadov Rajko,
Škorić Nemanja
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20782
Subject(s) - mathematics , hamiltonian path , hypergraph , combinatorics , lemma (botany) , discrete mathematics , conjecture , random graph , logarithm , embedding , mathematical proof , tuple , graph , ecology , mathematical analysis , geometry , poaceae , artificial intelligence , computer science , biology
We show that for every k ∈ N there exists C > 0 such that ifp k ≥ Clog 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 hypergraphG ( k ) ( n , p ) for p ≥ Clog 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.