Finding tight hamilton cycles in random hypergraphs faster

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 Clog3n/n . Our result partially answers a question of Dudek and Frieze (Random Struct Algorithms 42:374–385, 2013) who proved that tight Hamilton cycles exists 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 et al. (Random Struct Algorithms 46:446–465, 2015) 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≥n−1+ε , while the algorithm of Nenadov and Škorić is a randomised quasipolynomial time algorithm working for edge probabilities p≥Clog8n/n .