Decision problem for Hamilton $2$-cycles in $4$-graphs
2026-07-13 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study a special kind of cycle called a Hamilton 2-cycle in a 4-uniform hypergraph, which is a structure with edges connecting exactly four vertices. They find the exact conditions on how connected the hypergraph needs to be (measured by minimum codegree) to guarantee the existence of such a cycle, confirming a previous conjecture. Their results work when every triple of vertices appears in at least about one-third of all possible edges. They also provide a polynomial-time method to check for these cycles, which is notably different from similar problems in regular graphs where the problem is harder.
4-uniform hypergraphHamilton cycle2-cycleminimum codegreehypergraph connectivitypolynomial-time algorithmGarbe and Mycroft conjecturecombinatoricsgraph theorycomplexity
Authors
Luyining Gan, Jie Han, Bin Wang
Abstract
A $4$-uniform $2$-cycle in a $4$-uniform hypergraph of length $t$ is a cyclic ordering of $2t$ vertices $v_1v_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 $γ>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+γ)n$ edges and admits a Hamilton $2$-cycle. Up to the error term $γ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+γ)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)$.