ℓp-norm (codegree-power-sum) reformulation of Turán density: maximize Σ(codegree)^p instead of edge count

Statement

Setup (classical, ℓ1). For an $r$-uniform hypergraph $H$ and a host $r$-graph $G$ on $n$ vertices, the classical Turán density is $$\pi(H) = \lim_{n\to\infty} \frac{\mathrm{ex}(n,H)}{\binom{n}{r}}, \qquad \mathrm{ex}(n,H) = \max\{e(G): |V(G)|=n,\ G\ H\text{-free}\}$$ (Turán number ex(n,H): extremal edge-count for forbidden subgraphs). For 3-graphs, $e(G) = \tfrac13\sum_{\{x,y\}} d(x,y)$ where $d(x,y)$ is the codegree (number of edges containing both $x,y$) — i.e. $3\cdot e(G)$ is exactly the $\ell_1$-norm of the codegree vector $(d(x,y))_{\{x,y\}\in\binom{V}{2}}$.

The ℓp reformulation. Fix $p\ge1$ (and, in the general $(t,p)$-norm version, also a subset-size $t$, $1\le t<r$). Instead of maximizing the $\ell_1$-norm (edge count), maximize the $p$-th power sum of the $t$-degree ($t$-codegree) vector: $$\|G\|_{t,p} \;=\; \sum_{T\in\binom{V(G)}{t}} d_G(T)^p,$$ where $d_G(T)$ is the number of edges of $G$ containing the $t$-set $T$. Define the $(t,p)$-norm extremal function and density $$\mathrm{ex}_{t,p}(n,H) = \max\{\|G\|_{t,p} : |V(G)|=n,\ G\ H\text{-free}\}, \qquad \sigma_{t,p}(H) = \lim_{n\to\infty}\frac{\mathrm{ex}_{t,p}(n,H)}{n^{t+p(r-t)}}$$ (normalization exponent chosen so the limit is a bounded constant; concrete instances below use the specific normalizations each paper defines). (arxiv.org/abs/2406.15934, Chen–Iľkovič–León–Liu–Pikhurko, "Nondegenerate Turán problems under $(t,p)$-norms", direct fetch.)

Two special cases recover known objects: - $p=1$, any $t$: $\|G\|_{t,1} = \binom{r}{t}^{-1}\cdot t\text{-degree sum}$, a linear rescaling of the ordinary edge count — this *is* the classical Turán number/density $\mathrm{ex}(n,H)$, $\pi(H)$. - $t=2,p=2$ (3-graphs): $\|G\|_{2,2} = \sum_{\{x,y\}} d(x,y)^2 =: \mathrm{co}_2(G)$, the codegree squared sum, the square of the $\ell_2$-norm of the codegree vector; this is the object studied by Balogh–Clemen–Lidický (arxiv.org/abs/2108.10406, direct fetch: "the codegree squared sum $\mathrm{co}_2(G)$ ... is the sum of codegrees squared $d(x,y)^2$ over all pairs of vertices $x,y$").

Why "codegree-power-sum"

for $t<r$, $d_G(T)^p$ is literally "codegree to the $p$-th power," summed over all $t$-subsets $T$ — hence the family name. The case $t=r-1$ (i.e. $t$-sets are $(r-1)$-subsets of the $r$-edges) is the setting used for the 3-graph tetrahedron/Fano/cycle results below, where $t=2=r-1$ for $r=3$.

Facts

- Origin of the general idea: Caro–Yuster (2000), graphs, $t=1$. The graph-only precursor "degree power sum" $D_p(G)=\sum_v \deg(v)^p$ (i.e. $t=1$, ordinary vertex degree) was introduced as a Turán-type extremal quantity by Caro and Yuster, "A Turán Type Problem Concerning the Powers of the Degrees of a Graph" (math/0401398), asking for $D_p(n,H)=\max\{D_p(G): G$ is $n$-vertex $H$-free$\}$; $p=1$ recovers $2\,\mathrm{ex}(n,H)$. This graph-degree-power line has an active independent literature (e.g. arxiv.org/pdf/2404.07059 on $P_k$-free graphs, arxiv.org/pdf/2312.07005). - The hypergraph codegree version ($t=2,p=2$, 3-graphs) was launched by Balogh–Clemen–Lidický, "Hypergraph Turán Problems in $\ell_2$-Norm" (Surveys in Combinatorics 2022, arxiv.org/abs/2108.10406): they (asymptotically) determine $\mathrm{exco}_2(n,H)$ for matchings, stars, paths, cycles, and $F_{3,3}=F_5$ (5-vertex 3-graph with edges $\{123,124,345\}$), and pose the survey/conjecture framework the subsequent literature fills in. - Flagship application — Turán's tetrahedron problem, solved in $\ell_2$ though open in $\ell_1$. The classical $\pi(K_4^{(3)})$ (Turán's tetrahedron conjecture, Erdős #500 — Turán density of the tetrahedron $K_4^{3}$) is only pinned to $[5/9,\,0.5611666]$ (Razborov 2010 flag-algebra bound), open since 1941 and believed *unstable* (exponentially many non-isomorphic near-extremal constructions). Balogh–Clemen–Lidický (arxiv.org/abs/2108.10408) prove the $\ell_2$ analogue exactly: $\sigma(K_4^{(3)})=1/3$, with a full stability theorem, and Bodnár–Chen–Deng (arxiv.org/abs/2511.12506, Nov 2025) later prove the extremal construction $\mathbb{C}_n$ (Turán's own 1941-conjectured cyclic 3-partite hypergraph) is the unique $\ell_2$-maximizer for large $n$ — see 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) for the fully worked-out proof structure. The same paper gets $\sigma(K_5^{(3)})=5/8$ (construction $\mathcal{B}_n$, balanced complete bipartite 3-graph) by the identical machinery. - Fano plane: Andrásfai–Erdős–Sós-type stability in $\ell_2$. Hou–Liu–Zhang (arxiv.org/abs/2507.12354) prove that every Fano-plane-free 3-graph on $n$ vertices with minimum $\ell_2$-degree $\ge(5/4-\varepsilon)n^3$ must be bipartite for large $n$, confirming a Balogh–Clemen–Lidický conjecture, with the balanced complete bipartite 3-graph as the unique extremal construction — a direct 3-graph analogue of the classical Andrásfai–Erdős–Sós graph theorem transported into the $\ell_2$-norm setting. - Tight cycles and tight-cycle-minus-an-edge: a cluster of papers computes the *codegree Turán density* and its $\ell_2$-norm sibling for 3-uniform tight cycles (arxiv.org/abs/2211.12721 "The codegree Turán density of tight cycles minus one edge"; arxiv.org/abs/2408.02588 "The codegree Turán density of $3$-uniform tight cycles"; arxiv.org/abs/2507.00812 "Turán density of tight cycles minus one edge in the $\ell_2$-norm") — showing the reformulation is now a standard second attempt whenever a codegree-type Turán question resists the classical density approach. - Extremal set-theory analogues also transfer. Brooks–Linz (arxiv.org/abs/2310.09379) prove $\ell_2$-norm versions of the Erdős–Ko–Rado theorem and the Erdős Matching Conjecture for the codegree-squared-sum objective, and determine $\mathrm{exco}_2(n,H)$ exactly (not just asymptotically) for minimal/linear 3-paths and 3-cycles — showing the technique reaches beyond "forbid one small hypergraph" into the classical intersecting-family canon too. - General $(t,p)$-norm framework unifies and extends past $p=2$. Chen–Iľkovič–León–Liu–Pikhurko (arxiv.org/abs/2406.15934) build a general machinery for $\mathrm{ex}_{t,p}(n,H)$ for any $p>0$ (not just $p=2$), proving general asymptotic-extremal-value + stability theorems, resolving the case of expansions of graphs with chromatic number $>r$, giving exact results with strong stability for $p\ge1$, and resolving the generalized triangle $F_5$ in this general setting. - Kleitman–West connection. The Kleitman–West problem (maximizing the number of pairs with fixed codegree structure) is noted by Balogh–Clemen–Lidický as asymptotically equivalent to maximizing $\mathrm{co}_2(G)$ over hypergraphs of a fixed edge density — an example of a *pre-existing* extremal question turning out to already be an $\ell_2$-norm Turán problem in disguise.

WHEN it applies

whenever a classical ($\ell_1$/edge-count) Turán density $\pi(H)$ is suspected or known to be unstable — i.e. many pairwise non-isomorphic near-extremal constructions exist at the same edge density (this is exactly the obstruction flag-algebra + stability methods choke on, since Simonovits-style stability arguments need a *unique* extremal structure to converge to). It is also the natural move whenever the forbidden pattern $H$ or a related question is more naturally phrased in terms of codegrees/local structure rather than raw edge count (e.g. tight cycles, Fano-plane-type bipartite-stability questions, intersecting-family questions).

WHY it works (the mechanism)

1. Strict convexity breaks ties that linearity cannot. The classical objective $\sum_T d_G(T)$ ($p=1$) is *linear* in the degree/codegree vector, so it is indifferent to how a fixed total mass is spread across $T$'s — any redistribution that preserves the sum preserves the score. Raising to a power $p>1$ makes the objective strictly convex, so by the power-mean/Jensen inequality it *strictly rewards evenness*: among all degree vectors with a fixed $\ell_1$-sum, the one maximizing $\sum_T d(T)^p$ is the most balanced one satisfying the other constraints. This is precisely why $\ell_2$ collapsed the tetrahedron problem's huge family of $5/9$-density $\ell_1$-extremal constructions (Turán's cyclic $\mathbb{C}_n$, Kostochka's, Fon-der-Flaass's, Frohmader's) down to the single winner $\mathbb{C}_n$ — see 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) Facts and Technique for the full argument. 2. **The Cauchy–Schwarz/power-mean bridge back to $\ell_1$ is one-directional and lossy — which is *why* the two problems are genuinely different, not equivalent.** By Cauchy–Schwarz, $\big(\sum_T d(T)\big)^2 \le \binom{n}{t}\sum_T d(T)^2$, so an upper bound on $\mathrm{co}_2$ *does* imply an upper bound on the $\ell_1$-sum, but only at order $n^{(t+p(r-t))/2}$-type strength — generically far too weak to recover the sharp linear-order Turán density bound. Consequently a solved $\ell_p$-norm result almost never mechanically resolves the classical $\pi(H)$ question; it is a genuinely separate, usually easier, sibling problem that happens to frequently share the same conjectured extremal construction (this is what makes it valuable derivation fuel: proving the $\ell_p$ case first often reveals/confirms the right extremal structure and stability mechanism before the harder $\ell_1$ case is attempted). 3. The proof engine is still flag algebras, applied to a quadratic (or $p$-th degree) target instead of a linear one. Maximizing $\sum_T d(T)^p$ over $H$-free $n$-vertex $r$-graphs is first re-expressed as bounding a fixed linear combination of small-subgraph ("flag") densities in the limit object — the same Razborov flag-algebra semidefinite-programming machinery (Flag algebras — Razborov's SDP-based calculus for extremal graph/hypergraph densities) used for classical $\pi(H)$ computations, just fed a different (degree-$p$, not degree-$1$) target functional. This is why the $\ell_p$ reformulation is *computationally* no harder to set up than the classical problem — the payoff is entirely in the strict-convexity uniqueness gain described in point 1. 4. Stability bootstraps off classical ($\ell_1$) restricted-stability results rather than replacing them. In the tetrahedron case, Balogh–Clemen–Lidický's $\ell_2$-stability proof invokes Pikhurko's 2011 *restricted* classical stability theorem (for $K_4^{(3)}$-free graphs additionally forbidding a 4-set spanning exactly one edge) as a black box, then shows near-$\mathrm{co}_2$-optimal graphs can always be cheaply repaired (via the hypergraph removal lemma, 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) into that restricted regime. The general lesson: look for an existing *restricted* classical stability result for the same forbidden pattern before building an $\ell_p$-stability proof from scratch. 5. Exact uniqueness (beyond stability) needs local strictly-improving swap lemmas. Going from "near-extremal implies structurally close to the construction" (stability) to "the construction is the *unique* exact maximizer" requires a separate argument: identify "bad" edges (outside the construction) and "missing" edges (inside it but absent), and prove that swapping one for the other strictly increases the $\ell_p$-objective under mild degree conditions. Iterating forces uniqueness (Bodnár–Chen–Deng 2025's route to uniqueness for the tetrahedron problem). This local-swap technique is explicitly flagged by its authors as reusable for other $\ell_p$-norm (or even $\ell_1$) extremal problems.

Recombination recipe (how a solver uses this to attack a new problem)

1. Identify a Turán-type problem $\pi(H)$ (or a related codegree-type quantity) that is open, or open in a "clean unique-extremizer" sense, because of suspected/known instability — many non-isomorphic constructions tie at the conjectured density. 2. Reformulate as $\sigma_{t,p}(H) = \lim_n \mathrm{ex}_{t,p}(n,H)/n^{t+p(r-t)}$ for a natural choice of $(t,p)$ — $t=r-1,p=2$ (codegree-squared) is the best-tested default for 3-graphs; check arxiv.org/abs/2406.15934 for the general $(t,p)$ machinery if $p=2$ doesn't fit. 3. Set up the flag-algebra SDP for the new (degree-$p$) target functional — same computational pipeline as classical $\pi(H)$ flag-algebra work (Flag algebras — Razborov's SDP-based calculus for extremal graph/hypergraph densities), just a different linear combination of flag densities being bounded. 4. If/when an asymptotic bound is obtained, check whether it matches (in structure) a *known conjectured* $\ell_1$-extremal construction for the same $H$ — if so, that is strong independent evidence the classical conjecture has the right answer, even though it does not prove it. 5. For stability: search the classical-theory literature for a *restricted* stability result for $H$ (i.e. classical stability after also forbidding one extra small pattern) to use as a bootstrapping black box, then show near-$\ell_p$-extremal graphs can be cleaned into that restricted regime via hypergraph removal (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). 6. For uniqueness beyond stability: build a library of local bad-edge/missing-edge swap lemmas that strictly increase the $\ell_p$-objective, following Bodnár–Chen–Deng's template. 7. Explicitly report both results as separate facts: "$\sigma_{t,p}(H)=\ldots$ [proved]" is not "$\pi(H)=\ldots$ [proved]" — do not conflate them when writing up or recombining into further derivations; the $\ell_1$ problem remains open unless independently closed.

Related

- Turán number ex(n,H): extremal edge-count for forbidden subgraphs — the classical $\ell_1$ / edge-count framework $\mathrm{ex}(n,H)$, $\pi(H)$ that this whole family of techniques reformulates; $p=1$ recovers it exactly. - Flag algebras — Razborov's SDP-based calculus for extremal graph/hypergraph densities — the SDP proof engine used to obtain the asymptotic $\ell_p$-norm bounds (Razborov's method, applied here to a degree-$p$ rather than degree-$1$ target functional). - 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 removal-lemma cleaning step used to bootstrap $\ell_p$-stability from restricted classical ($\ell_1$) stability results. - Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) — the excess-count argument used to prove blow-up invariance of the $\ell_p$-norm density $\sigma_{t,p}(F)$, mirroring the classical Turán-density fact. - Erdős #500 — Turán density of the tetrahedron $K_4^{3}$ — Turán's classical tetrahedron problem ($\pi(K_4^{(3)})\in[5/9,0.5611666]$, open); the motivating hard instance whose $\ell_2$-norm sibling is fully solved. - Erdős #712 — Turán density of complete $r$-uniform hypergraphs $K_k^r$ — the general $\pi(K_k^{(r)})$ Turán-density problem for all $k>r>2$ ($\$1000$ prize, open); the $\ell_p$-norm reformulation is a template for attacking *sibling* questions about the same forbidden family even where the headline $\ell_1$ prize problem stays out of reach. - 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) — the fully worked flagship application: $\sigma(K_4^{(3)})=1/3$ and $\sigma(K_5^{(3)})=5/8$, with the complete asymptotic-bound + stability + uniqueness proof structure that this page's Technique section abstracts into a general recipe.