Projects per year
Abstract
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 polynomialtime 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 NPhard to determine if a graph is Hamiltonian. We also consider tight Hamilton cycles in $k$uniform hypergraphs $H$ for $k \geq 3$, giving a series of reductions to show that it is NPhard to determine whether a $k$uniform hypergraph $H$ with minimum degree $\delta(H) \geq \frac{1}{2}V(H)  O(1)$ contains a tight Hamilton cycle. It is therefore unlikely that a similar characterisation can be obtained for tight Hamilton cycles.
Original language  English 

Journal  Journal of Combinatorial Theory. Series B 
Early online date  9 May 2018 
DOIs  
Publication status  Epub ahead of print  9 May 2018 
Keywords
 Hamilton cycles
 Hypergraphs
Fingerprint
Dive into the research topics of 'Hamilton cycles in hypergraphs below the Dirac threshold'. Together they form a unique fingerprint.Projects
 1 Finished

Embeddings in hypergraphs
Engineering & Physical Science Research Council
30/03/15 → 29/03/17
Project: Research Councils