Decision problem for Hamilton $2$-cycles in $4$-graphs

Abstract

A $4$-uniform $2$-cycle in a $4$-uniform hypergraph of length $t$ is a cyclic ordering of $2t$ vertices $v_1{v}_2\cdots v_{2t}{v}_1$ such that $v_{2i+1}{v}_{2i+2}{v}_{2i+3}{v}_{2i+4}$ are edges for $0\le i\le t-1$ while the addition is modulo $2t$. For every ${\hat{I}}^3>0$ and large $n$, we characterize the $n$-vertex $4$-uniform hypergraphs such that every triple of vertices is contained in at least $(1/3+{\hat{I}}^3)n$ edges and admits a Hamilton $2$-cycle. Up to the error term ${\hat{I}}^{3}n$, the assumption on the minimum codegree is best possible and verifies a conjecture of Garbe and Mycroft. As a consequence, this gives a polynomial-time algorithm that decides whether an $n$-vertex $4$-uniform hypergraph with minimum codegree $(1/3+{\hat{I}}^3)n$ contains a Hamilton $2$-cycle. This stands as a steep contrast to the graph case where such a hardness gap has size $o(n)$.

43 pages