Tight Hamilton Cycles in Linearly Quasirandom 3-Graphs

Abstract

We study tight Hamilton cycles in linearly quasirandom $3$-graphs. An $n$-vertex $3$-graph $H$ is $(p,\mu )$-dense if $e_H(X,Y,Z)\ge p|X||Y||Z|-\mu n^3$ for all $X,Y,Z\subseteq V(H)$. Araújo, Piga and Schacht asked whether the conditions $p,\alpha >1/4$ and ${\delta }_2(H)\ge \alpha n$ force a tight Hamilton cycle. We give a negative answer to this question. More generally, we determine the asymptotically sharp minimum-codegree threshold for the existence of a tight Hamilton cycle for every density $p\in (0,1)$. The resulting threshold is a discontinuous piecewise-defined function with four distinct regimes, and matching constructions show that every piece is best possible. The proof combines the absorption method and a fixed-length connecting lemma above density $1/3$ with a canonical-component Hamilton framework at and below density $1/3$.

44 pages, 1 figure