Turán's tetrahedron conjecture solved in the ℓ2-norm: codegree-squared-sum density σ(K₄³) = 1/3, uniquely extremal (Balogh–Clemen–Lidický 2021/2022; uniqueness by Bodnár–Chen–Deng 2025)

Statement

Let $K_4^{(3)}$ (the tetrahedron) be the complete 3-uniform hypergraph on 4 vertices (all $\binom43=4$ triples present). For an $n$-vertex 3-uniform hypergraph $G$ and a pair of vertices $x,y$, let $d(x,y)$ be the codegree — the number of edges containing both $x$ and $y$. Define the codegree squared sum $$\mathrm{co}_2(G) \;=\; \sum_{\{x,y\}\subset V(G)} d(x,y)^2,$$ i.e. the square of the $\ell_2$-norm of the codegree vector (as opposed to the classical $\ell_1$-norm $\sum d(x,y) = 3\cdot e(G)$, whose maximization *is* Turán's original tetrahedron problem, Erdős #500 — Turán density of the tetrahedron $K_4^{3}$). Let $$\mathrm{exco}_2(n,K_4^{(3)}) = \max\{\mathrm{co}_2(G) : |V(G)|=n,\ G\ \text{is } K_4^{(3)}\text{-free}\},\qquad \sigma(K_4^{(3)}) = \lim_{n\to\infty}\frac{\mathrm{exco}_2(n,K_4^{(3)})}{\binom{n}{2}(n-2)^2}.$$

Question (Balogh–Clemen–Lidický 2021)

what is $\sigma(K_4^{(3)})$, and what are the extremal hypergraphs?

This is a norm-change reformulation of the still-open classical Turán tetrahedron problem (Erdős #500 — Turán density of the tetrahedron $K_4^{3}$, $\pi(K_4^{(3)})\in[5/9,\,0.5611666]$, open since 1961): same forbidden pattern $K_4^{(3)}$, same host hypergraphs, but the objective being maximized is switched from $\ell_1$ (edge count) to $\ell_2$ (sum of squared codegrees) of the codegree vector.

Facts

- Fully solved, in two stages: Balogh, Clemen, Lidický (arXiv:2108.10408, *J. Lond. Math. Soc.* 106(1):60–84, 2022) proved the asymptotic value $\sigma(K_4^{(3)})=1/3$ plus a stability theorem; Bodnár, Chen, Deng (arXiv:2511.12506, Nov 2025) then proved the sharp uniqueness of the extremal construction for all sufficiently large $n$, closing the gap left open by BCL's 2021 conjecture. - Answer: $\sigma(K_4^{(3)}) = 1/3$, and $\sigma(K_5^{(3)}) = 5/8$ (BCL prove both cases with the same machinery). - Extremal construction $\mathcal{C}_n$ — *exactly Turán's own conjectured $\ell_1$-extremal construction*: partition $V$ into three near-equal parts $V_1,V_2,V_3$; edges are all "rainbow" triples $\{a,b,c\}$ with $a\in V_1,b\in V_2,c\in V_3$, together with triples $\{a,b,c\}$ with $a,b\in V_i,\,c\in V_{i+1}$ (indices mod 3, i.e. two-in-one-part-plus-next-part triples). This is precisely the "balanced complete cyclic 3-partite 3-graph" $\mathbb{C}_n$ that is one of Turán's conjectured extremizers for the classical (unsolved) $\ell_1$ problem. - Uniqueness theorem (Bodnár–Chen–Deng 2025, Thm 1.2): for $n$ large enough, if $H$ is an $n$-vertex $K_4^{(3)}$-free 3-graph then $\|H\|_2 \le \|\mathbb{C}_n\|_2$, with equality iff $H\cong \mathbb{C}_n$ — i.e. among the *exponentially many* pairwise non-isomorphic hypergraphs conjectured to be $\ell_1$-extremal for Turán's original problem (Brown; Kostochka; Fon-der-Flaass; Frohmader constructions — see Erdős #500 — Turán density of the tetrahedron $K_4^{3}$), squaring the codegree vector kills all of them except $\mathbb{C}_n$. - Stability (BCL 2021, Thm 1.5): for every $\varepsilon>0$ there is $\delta>0,n_0$ such that any $K_4^{(3)}$-free $n>n_0$-vertex $G$ with $\mathrm{co}_2(G) \ge \left(\tfrac13-\delta\right)\binom{n}{2}(n-2)^2$ is $\varepsilon$-close (in edit distance) to $\mathbb{C}_n$ — this holds unconditionally, unlike the analogous $\ell_1$ result, which (Pikhurko 2011) only holds after *additionally* forbidding 4-sets spanning exactly 1 edge. - The $K_5^{(3)}$ sibling case works the same way: $\sigma(K_5^{(3)})=5/8$, extremal construction $\mathcal{B}_n$ (balanced complete bipartite 3-graph: all triples meeting both parts), with an analogous stability theorem (BCL Thm 1.6). - A related exact (non-asymptotic) result: BCL also determine $\mathrm{exco}_2(n,F_{3,3})$ exactly (not just asymptotically) for all $n\ge n_0$, with $\mathcal{B}_n$ again the unique extremizer (Theorem 1.7), via a full stability-plus-cleaning argument — demonstrating the $\ell_2$ machinery can go all the way to an exact extremal number, not merely an asymptotic density. - General structural facts proved for $\mathrm{exco}_2(n,\cdot)$ in general (BCL, Props 1.8–1.9): the scaled limit $\sigma(F)=\lim_n \mathrm{exco}_2(n,F)/\binom{n}{2}(n-2)^2$ always exists; $\sigma$ is invariant under blowing up $F$ (mirroring the analogous classical Turán-density fact); and a supersaturation theorem holds (excess $\mathrm{co}_2$ above $\sigma(F)\binom{n}{2}(n-2)^2$ forces $\Omega(n^{|V(F)|})$ copies of $F$) — the supersaturation result is what lets blow-up invariance transfer over from the $\ell_1$ theory. - Contrast with the still-open $\ell_1$ problem: the classical Turán tetrahedron density is only pinned to $\pi(K_4^{(3)})\in[5/9,\,0.5611666]$ (Razborov 2010 flag-algebra upper bound, unimproved as of 2026 — Erdős #500 — Turán density of the tetrahedron $K_4^{3}$), and is believed to lack stability entirely (exponentially many non-isomorphic near-$5/9$ constructions). The $\ell_2$ reformulation is a genuinely *different, easier* problem that happens to share the extremal construction with the $\ell_1$ conjecture, and it is now completely closed (asymptotic value + stability + uniqueness), while the original $\ell_1$ question these results were inspired by remains one of the most famous open problems in extremal combinatorics.

Solution

Answer: $\sigma(K_4^{(3)}) = 1/3$, uniquely achieved (for large $n$) by the balanced cyclic 3-partite construction $\mathbb{C}_n$ — Turán's own 1941-conjectured extremal hypergraph for the (still unsolved) classical problem.

**The transferable technique — why squaring the codegree vector *breaks the symmetry* that blocks the classical problem:**

1. Flag algebras give the asymptotic upper bound (BCL 2021). Question 1.1 (maximize $\mathrm{co}_2$ over $K_4^{(3)}$-free $n$-vertex 3-graphs) is first shown to be equivalent to bounding a specific linear combination of *4-vertex subgraph densities* in large $K_4^{(3)}$-free hypergraphs (§3.3 of BCL). This recasts the $\ell_2$ objective — a *quadratic* function of the codegree vector, not the linear edge-count that ordinary Turán density is — into a form Razborov's flag-algebra semidefinite-programming machinery can still attack: the SDP searches for a sum-of-squares certificate bounding that combination, exactly the same computational engine used for the classical (still-unresolved) $5/9$ vs. $0.5611666$ gap, but applied to the *squared* objective instead of the linear one. The computation is mechanical (solver-verified), giving Theorem 1.2's $\sigma(K_4^{(3)})=1/3$ directly. 2. The key structural reason squaring helps: it penalizes uneven codegree distributions, which is exactly what made the $\ell_1$ problem unstable. The classical tetrahedron problem's notorious obstruction is that *many* combinatorially different constructions (Turán's cyclic $\mathbb{C}_n$, but also Kostochka's, Fon-der-Flaass's, Frohmader's families) all achieve the same linear ($\ell_1$) density $5/9$ — because $\ell_1$ only sees the *total* codegree mass, indifferent to how it is spread across vertex pairs. $\mathrm{co}_2$, being a sum of *squares*, strictly prefers codegree vectors that are as evenly spread as possible for a given total — by the QM-AM / Cauchy–Schwarz inequality, any deviation from Turán's perfectly-regular cyclic construction costs $\mathrm{co}_2$-mass even if it costs zero $\ell_1$-mass. This is the transferable idea: when an $\ell_1$-extremal problem is degenerate/unstable because of a large symmetry class of equally-good constructions, re-optimizing the same forbidden-pattern problem in $\ell_2$ (or a higher $\ell_p$) can collapse that symmetry class down to a single winner, because higher norms are strictly convex and thus uniquely reward "flatness" among ties of the lower norm. BCL make this precise via a full stability theorem (Theorem 1.5): near-$\mathrm{co}_2$-optimal $K_4^{(3)}$-free graphs must be structurally close to $\mathbb{C}_n$ — unconditionally, with no extra forbidden-pattern restriction needed (contrast Pikhurko's $\ell_1$ stability result, which only closes after also forbidding 4-sets with exactly 1 edge). 3. Bootstrapping the stability proof itself reuses the (harder, unsolved-in-general) $\ell_1$ machinery as an ingredient, not a competitor. BCL's proof of Theorem 1.5 does not avoid the classical theory — it invokes Pikhurko's 2011 *restricted* $\ell_1$-stability result (Theorem 5.2: $K_4^{(3)}$-free graphs with no 4-set spanning exactly 1 edge, achieving near-$5/9$ density, are close to $\mathbb{C}_n$) as a black box, then shows any $\mathrm{co}_2$-near-extremal graph can be cleaned (via the Rödl–Schacht hypergraph-removal lemma, their Theorem 3.2) into the regime where Pikhurko's restricted theorem applies, without losing more than $o(1)$ of the $\mathrm{co}_2$-mass. The transferable move: **when the target $\ell_p$-norm problem is intractable directly, look for an existing *restricted* stability result in the classical ($\ell_1$) theory and show that near-$\ell_p$-optimal graphs can always be locally repaired into that restricted regime cheaply. 4. Pushing from stability to exact uniqueness needs a genuinely new local-modification technique (Bodnár–Chen–Deng 2025).** BCL's 2021 stability theorem only says near-extremal graphs are *close to* $\mathbb{C}_n$, leaving open whether $\mathbb{C}_n$ is the *unique* exact maximizer (their Conjecture 1.3). The 2025 paper closes this via two new tools: (a) a Mantel-type theorem for vertex-colored graphs that forbid certain "cyclically-colored triangle" patterns, itself proved via a large computer-assisted flag-algebra computation (1968 five-vertex flags) bounding the $\ell_2$-norm of such colored graphs by $9n^3+\varepsilon n^3$; and (b) an "enhanced Simonovits stability" procedure that, rather than fully characterizing near-extremal structure, works by identifying "bad edges" (edges of $H$ outside $\mathbb{C}_n$'s edge set) and "missing edges" (edges of $\mathbb{C}_n$ absent from $H$) and proving *local swap lemmas*: under mild degree conditions, swapping a bad edge for a missing edge strictly increases $\mathrm{co}_2$. Iterating these strictly-improving local swaps shows any non-isomorphic-to-$\mathbb{C}_n$ near-extremal graph can be strictly improved, forcing exact uniqueness. This "reduce global uniqueness to a library of local strictly-improving edge-swaps, rather than a full structural classification" strategy is explicitly flagged by the authors as reusable for other extremal ($\ell_2$-norm or otherwise) hypergraph problems.

Why this matters for open problems that depend on it: this result is the clearest existence proof that the $\ell_p$-norm reformulation of a Turán-type problem is a genuinely different (and sometimes tractable) question from the classical $\ell_1$ density, even when it shares the same forbidden pattern and the same conjectured extremal construction. It gives a concrete template — flag-algebra SDP for the asymptotic bound, invoke/adapt an existing restricted classical-theory stability result to bootstrap full stability, then local strictly-improving swap lemmas for exact uniqueness — for attacking *other* Turán problems (e.g. $K_5^{(3)}$, already done by the same authors; $F_{3,3}$, done exactly; and in principle any hypergraph Turán problem currently stuck in the $\ell_1$ setting due to non-uniqueness/instability of its extremal family) via the $\ell_2$-norm side door, without needing to resolve the underlying classical $\ell_1$ problem itself. The classical Turán tetrahedron problem (Erdős #500 — Turán density of the tetrahedron $K_4^{3}$, $\$500$ prize) remains completely open.

Related

- Erdős #500 — Turán density of the tetrahedron $K_4^{3}$ — Turán's classical (unsolved, $\ell_1$-norm / raw edge-count) tetrahedron problem, $\pi(K_4^{(3)})\in[5/9,0.5611666]$; this page's $\ell_2$-norm result is explicitly cross-linked there as a solved sibling sharing the same conjectured extremal construction $\mathbb{C}_n$. - Erdős #712 — Turán density of complete $r$-uniform hypergraphs $K_k^r$ — the general Turán density problem $\pi(K_k^{(r)})$ for all $k>r>2$ ($\$1000$ prize); #500 is its $(r,k)=(3,4)$ special case, itself the hardest well-studied member. - Uniform Turán density of the broken tetrahedron K_4^{(3)-} equals 1/4 (Erdős–Sós problem, solved 2013–2016 by two independent methods) — a different (uniform-Turán-density) solved refinement of the tetrahedron problem, $\pi_u(K_4^{(3)-})=1/4$, also proved by flag algebras (independently) plus hypergraph-regularity, and also explicitly framed by its authors as a stepping stone toward the still-open full tetrahedron question — a sibling illustration of "reformulate the norm/density notion to make an intractable Turán problem tractable." - Turán number ex(n,H): extremal edge-count for forbidden subgraphs — the classical $\ell_1$ Turán-number framework this page's $\ell_2$ reformulation modifies. - Hypergraph regularity / Gowers uniformity norms and density-increment arguments: quasirandom decomposition + counting/removal lemmas, and the iterative-density-increase route to Szemerédi-type theorems — supplies the Rödl–Schacht removal-lemma-type cleaning step (Theorem 3.2 of BCL) used to bootstrap the $\ell_2$ stability proof from Pikhurko's restricted $\ell_1$ stability result. - Stability method — bootstrapping an asymptotic extremal bound into an exact/unique result via 'near-extremal ⇒ structurally close to extremal' — Simonovits/Pikhurko-style stability, both as an ingredient (Pikhurko's restricted $\ell_1$ result) and as the object being strengthened ("enhanced Simonovits stability" via local swap lemmas) in the 2025 uniqueness proof. - Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) — used by BCL to prove blow-up invariance of the codegree-squared density $\sigma(\cdot)$ in general. - Primary sources: J. Balogh, F.C. Clemen, B. Lidický, "Solving Turán's Tetrahedron Problem for the $\ell_2$-Norm," arXiv:2108.10408, *J. Lond. Math. Soc.* (2) 106(1):60–84 (2022); L. Bodnár, W. Chen, J. Deng (et al.), "Tetrahedron Conjecture in the $\ell_2$-norm," arXiv:2511.12506 (Nov 2025).