The Codegree Threshold for 3-Graphs with Independent Neighborhoods

Source abstract

Given a family of 3-graphs $\mathcal{F}$, we define its codegree threshold $\mathrm{coex}(n, \mathcal{F})$ to be the largest number $d=d(n)$ such that there exists an $n$-vertex 3-graph in which every pair of vertices is contained in at least $d$ 3-edges but which contains no member of $\mathcal{F}$ as a subgraph. Let $F_{3,2}$ be the 3-graph on $\{a,b,c,d,e\}$ with 3-edges $abc$, $abd$, $abe$, and $cde$. In this paper, we give two proofs that $\mathrm{coex}(n, \{F_{3,2}\})= \big(\frac{1}{3}+o(1)\big)n,$ the first by a direct combinatorial argument and the second via a flag algebra computation. Information extracted from the latter proof is then used to obtain a stability result, from which in turn we derive the exact codegree threshold for all sufficiently large $n$: $\mathrm{coex}(n, \{F_{3,2}\})= \lfloor n/3 \rfloor-1$ if $n$ is congruent to $1$ modulo $3$, and $\lfloor n/3 \rfloor$ otherwise. In addition we determine the set of codegree-extremal configurations for all sufficiently large $n$.