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 $p,\alpha>1/4$ together with $\delta_2(H)\ge\alpha n$ force a tight Hamilton cycle. We give a negative answer: for every $\varepsilon,\mu>0$ and all sufficiently large $n$, there exists an $n$-vertex $(p_0-\varepsilon,\mu)$-dense 3-graph $H$ with $\delta_2(H)\ge(p_0-\varepsilon)n$ and no tight Hamilton cycle, where $p_0:=\max_{0\le x\le1}\min\{x^3,1-x\}\approx0.317672$.
For every $p>1/3$, we determine the asymptotically sharp minimum-codegree threshold. Writing \[
\delta_0(p)=
\left(\frac{1-\sqrt{(4p-1)/3}}{2}\right)^2, \] we prove that every sufficiently large $(p,\mu)$-dense 3-graph $H$ with $\delta_2(H)\ge\alpha n$ contains a tight Hamilton cycle whenever $\alpha>\delta_0(p)$ and $\mu$ is sufficiently small. A matching construction shows that this threshold is best possible. The proof uses absorption together with a new fixed-length connecting lemma based on a regular slice, a directed pair-state graph, and a finite scalar lemma.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요