Tight Hamilton cycles in random hypergraphs
Allen, P.
, Böttcher, J., Kohayakawa, Y. & Person, Y.
(2015).
Tight Hamilton cycles in random hypergraphs.
Random Structures and Algorithms,
46(3), 446-465.
https://doi.org/10.1002/rsa.20519
, Böttcher, J., Kohayakawa, Y. & Person, Y.
(2015).
Tight Hamilton cycles in random hypergraphs.
Random Structures and Algorithms,
46(3), 446-465.
https://doi.org/10.1002/rsa.20519
We give an algorithmic proof for the existence of tight Hamilton cycles in a random r-uniform hypergraph with edge probability p=n-1+ε for every ε>0. This partly answers a question of Dudek and Frieze (Random Struct Algor 42 (2013), 374-385), who used a second moment method to show that tight Hamilton cycles exist even for p=ω(n)/n(r≥3) where ω(n)→∞ arbitrary slowly, and for p=(e+o(1))/n(r≥4). The method we develop for proving our result applies to related problems as well.