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^3n/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 $rge 4$ using a second moment argument. Moreover our algorithm is superior to previous results of Allen, Bottcher, Kohayakawa and Person [Random Structures & Algorithms 46 (2015), 446-465] and Nenadov and v{S}koric [arXiv:1601.04034] in various ways: the algorithm of Allen et al. is a randomised polynomial time algorithm working for edge probabilities $pge n^{-1+varepsilon}$, while the algorithm of Nenadov and v{S}koric is a randomised quasipolynomial time algorithm working for edge probabilities $pge Clog^8n/n$.
تحميل البحث