Finding tight Hamilton cycles in random hypergraphs faster. (23rd March 2021) - Allen, Peter; Koch, Christoph; Parczyk, Olaf; Person, Yury
Abstract: In an r -uniform hypergraph on n vertices, a tight Hamilton cycle consists of n edges such that there exists a cyclic ordering of the vertices where the edges correspond to consecutive segments of r vertices. We provide a first deterministic polynomial-time algorithm, which finds a.a.s. tight Hamilton cycles in random r -uniform hypergraphs with edge probability at least C log 3 n / n . Our result partially answers a question of Dudek and Frieze, who proved that tight Hamilton cycles exist already for p = ω (1/ n ) for r = 3 and p = ( e + o (1))/ n for r 4 using a second moment argument. Moreover our algorithm is superior to previous results of Allen, Böttcher, Kohayakawa and Person, and Nenadov and Škorić, in various ways: the algorithm of Allen et al. is a randomized polynomial-time algorithm working for edge probabilities p n^ - 1 + ε, while the algorithm of Nenadov and Škorić is a randomized quasipolynomial-time algorithm working for edge probabilities p C olimits^8 n/n .