Finding tight Hamilton cycles in random hypergraphs faster

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 [Random Structures & Algorithms 42 (2013), 374-385] who proved that tight Hamilton cycles exists already for $p=\omega (1/n)$ for $r=3$ and $p=(e+o(1))/n$ for $r\ge 4$ using a second moment argument. Moreover our algorithm is superior to previous results of Allen, Böttcher, Kohayakawa and Person [Random Structures & Algorithms 46 (2015), 446-465] and Nenadov and Škorić [arXiv:1601.04034] in various ways: the algorithm of Allen et al. is a randomised polynomial time algorithm working for edge probabilities $p\ge n^{-1+\epsilon }$, while the algorithm of Nenadov and Škorić is a randomised quasipolynomial time algorithm working for edge probabilities $p\ge C{\log }^{8}n/n$.

17 pages

References in corpus (3)

• Embedding bounded degree spanning trees in random graphs
• How many random edges make a dense graph hamiltonian?
• On Weak Hamiltonicity of a Random Hypergraph