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 Clog~3n. 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) for r = 3 and p = (e + o(l)) 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 Skoric (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 Skoric is a randomised quasipolynomial time algorithm working for edge probabilities p ≥ Clog~8 n.
展开▼
