Hamilton cycles in hypergraphs below the Dirac threshold

We establish a precise characterisation of 4-uniform hypergraphs with minimum codegree close to n/2 which contain a Hamilton 2-cycle. As an immediate corollary we identify the exact Dirac threshold for Hamilton 2-cycles in 4-uniform hypergraphs. Moreover, by derandomising the proof of our characterisation we provide a polynomial-time algorithm which, given a 4-uniform hypergraph H with minimum codegree close to n/2, either finds a Hamilton 2-cycle in H or provides a certificate that no such cycle exists. This surprising result stands in contrast to the graph setting, in which below the Dirac threshold it is NP-hard to determine if a graph is Hamiltonian. We also consider tight Hamilton cycles in k-uniform hypergraphs H for k≥3, giving a series of reductions to show that it is NP-hard to determine whether a k-uniform hypergraph H with minimum degree δ(H)≥12|V(H)|−O(1) contains a tight Hamilton cycle. It is therefore unlikely that a similar characterisation can be obtained for tight Hamilton cycles.