Stability method — bootstrapping an asymptotic extremal bound into an exact/unique result via 'near-extremal ⇒ structurally close to extremal'

Statement

Informal idea. For an extremal problem $\mathrm{ex}(n,\mathcal L)$ (or a hypergraph Turán density $\pi(\mathcal L)$) whose extremal examples are conjectured or known to be *essentially unique*, the stability method upgrades "I know the asymptotic extremal number" into "I know the *exact* extremal number and its *unique* extremizer, for all large $n$" — via an intermediate structural statement: *every* graph with edge count close to the extremum must itself be structurally close (small edit distance) to the conjectured extremal example.

The classical Erdős–Simonovits stability theorem. Let $\mathcal L$ be a finite family of forbidden graphs with $p+1 := \min\{\chi(L): L\in\mathcal L\}\ge 3$ (i.e. the non-degenerate, non-bipartite regime where Erdős–Stone–Simonovits gives $\mathrm{ex}(n,\mathcal L) = (1-\tfrac1p+o(1))\binom n2$; see Turán number ex(n,H): extremal edge-count for forbidden subgraphs). Then for every $\varepsilon>0$ there exist $\delta>0$ and $n_0$ such that whenever $n>n_0$ and $G$ is an $n$-vertex $\mathcal L$-free graph with $$e(G) \;\ge\; \Big(1-\frac1p\Big)\binom n2 - \delta n^2,$$ one can add and delete at most $\varepsilon n^2$ edges of $G$ to obtain the Turán graph $T_{n,p}$ — i.e. $|E(G)\,\triangle\,E(T_{n,p})| \le \varepsilon n^2$ (Füredi, arXiv:1501.03129, eq. (2), attributing the result to Erdős–Simonovits, Erdős, and Simonovits [1968]).

Keevash's $K_t$-free special case (survey Theorem 5.1). For every $\varepsilon>0$ there is $\delta>0$ such that if $G$ is $K_t$-free with $e(G)\ge(1-\delta)\,\mathrm{ex}(n,K_t)$ edges, then there is a partition $V(G)=V_1\cup\cdots\cup V_{t-1}$ with $\sum_i e(V_i) < \varepsilon n^2$ (people.maths.ox.ac.uk/keevash/papers/turan-survey.pdf, §5).

A sharper, quantifier-free form (Füredi's Theorem 1 / Corollary 2, the $\mathcal L=\{K_{p+1}\}$ case). If $K_{p+1}\not\subset G$, $|V(G)|=n$, and $e(G)=e(T_{n,p})-t$ for some $t\ge0$, then $G$ contains an (at most) $p$-chromatic subgraph $H_0\subseteq G$ with $e(H_0)\ge e(G)-t$; consequently there is a complete $p$-partite graph $K$ on $V(G)$ with $|E(G)\triangle E(K)|\le 3t$. This version has no $\varepsilon,\delta,n_0$ — it holds for *every* $n,p,t$ — and is proved via a short, elementary "delete then re-add" argument rather than Szemerédi's regularity lemma (Füredi arXiv:1501.03129, Theorem 1 / Corollary 2).

Hypergraph / general-metric form (Pikhurko's "graphit" reformulation). An $r$-graph $F$ is stable if for every $\varepsilon>0$ there are $\delta>0,n_0$ such that any two $F$-free $r$-graphs $G,G'$ on $n>n_0$ vertices, each with at least $(\pi(F)-\delta)\binom nr$ edges, can be obtained from one another by adding/deleting at most $\varepsilon n^r$ edges. Pikhurko (Disc. Math. 310 (2010), "An analytic approach to stability") shows this is equivalent to: the space of graphon/hypergraphon limits of near-extremal $F$-free sequences (their *graphits*, $\delta_2$-equivalence classes) is a single point (Keevash survey, §10, quoting Theorem 15 of Pikhurko's paper).

Facts

- Origin and co-discovery. The result traces to M. Simonovits, "A method for solving extremal problems in graph theory, stability problems," in *Theory of Graphs* (Proc. Colloq., Tihany, 1966), Academic Press/Akadémiai Kiadó, 1968, pp. 279–319 — Füredi's paper explicitly credits the theorem to "Erdős and Simonovits [Erdős–Simonovits 1966], Erdős [1967, two papers], and Simonovits [1968]" jointly (arXiv:1501.03129, §1). It is frequently (if slightly imprecisely) folded together with the Erdős–Stone theorem as the "Erdős–Stone–Simonovits theorem." - Two independent modern reproofs exist beyond the original combinatorial one: (a) Füredi's 2015 regularity-lemma-based proof (arXiv:1501.03129) derives Simonovits' stability as a corollary of the sharper, regularity-free Theorem 1 above plus one application of Szemerédi's regularity lemma to bridge $\mathcal L$-freeness for a general family down to the $K_{p+1}$-free case; (b) Pikhurko's 2010 analytic/graphon-limit proof (Disc. Math. 310) is "much more complicated than a straightforward approach, but may point the way to other stability results that cannot be obtained by simpler methods" (Keevash survey, §10) — i.e. it generalizes more readily to settings without a convenient regularity lemma. - The reusable four-step proof template (Keevash survey, end of §5, describing the standard shape of a stability-method *proof of the stability theorem itself*, as distinct from downstream applications): (i) show $G$ must have high minimum degree (else delete low-degree vertices without hurting the edge count much); (ii) $G$ has approximately the right global structure, so fix an optimal vertex-partition; (iii) show only a vanishing fraction of vertices have "bad" degree with respect to that partition; (iv) show there are essentially no "bad" edges (edges inside a part, or missing across parts) — worked concretely for $\mathrm{ex}(n,C_5)=\lfloor n^2/4\rfloor$ in Keevash's Lemma 5.2 sketch. - Andrásfai–Erdős–Sós theorem — the "exact, no-$\varepsilon$" sibling. Andrásfai, Erdős, Sós (Discrete Math. 8 (1974), 205–218, cited in Keevash's bibliography [7]) prove: any triangle-free graph $G$ on $n$ vertices with minimum degree $\delta(G) > 2n/5$ is bipartite — no error terms at all. Keevash calls this "a variant form of the stability approach": instead of "close to extremal density $\Rightarrow$ close to extremal structure," it says "high enough minimum degree (a purely local hypothesis) $\Rightarrow$ *exactly* extremal structure." The bound $2n/5$ is tight, witnessed by the blow-up of the Petersen-graph-adjacent Andrásfai graph built from the 5-cycle $C_5$. - Removal lemma $\Longleftrightarrow$ stability, given uniqueness (a general hypergraph mechanism). Keevash's survey shows the following chain for a family $F^{(t)}$ built by "expanding" a base family $F$: supersaturation (few excess edges over $\mathrm{ex}(n,F)$ still forces $\gg n^{v(F)}$ copies of $F$; Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983)) plus the hypergraph removal lemma (few copies of $F$ $\Rightarrow$ can delete $o(n^r)$ edges to kill them all) together show any two near-extremal $F$-free hypergraphs can be edited into each other in $o(n^r)$ edges — i.e. stability of $F$ follows automatically from supersaturation + the removal lemma, once $\pi(F^{(t)})=\pi(F)$ is known; this is the exact mechanism Pikhurko used (via Mubayi's stability of $H^r_t$) to reach the extended-complete-graph exact result (Keevash survey, end of §5). Because the removal lemma's quantitative dependence is typically tower-type (regularity-lemma-derived; see 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), this route proves stability *qualitatively* but with astronomically bad constants — useful for existence, not for optimizing $\delta(\varepsilon)$. - Canonical worked hypergraph success: the Fano plane. Füredi–Simonovits and (independently) Keevash–Sudakov prove the exact Turán number of the Fano-plane 3-graph for large $n$ by (a) proving a stability result (near-extremal Fano-free 3-graphs are close to bipartite-derived) and then (b) proving the sharper, $\varepsilon$-free statement "if $\delta(G) > (3/4-\delta)\binom n2$ and $G$ is Fano-free then $G$ is exactly bipartite" — an Andrásfai–Erdős–Sós-style minimum-degree refinement that Keevash notes is "equivalent in difficulty" to the stability result itself, via the same second-stage "defect" argument. Person & Schacht (SODA '09, ref [151]) then show the companion *counting* refinement: almost all Fano-free 3-graphs on $n$ vertices are bipartite. - Canonical worked success combining stability with an independent asymptotic tool: Pikhurko on the restricted tetrahedron. Razborov (2010, flag algebras) proved the asymptotic bound $e(G)\le(5/9+o(1))\binom n3$ for 3-graphs $G$ in which no 4-set spans exactly 1 or exactly 4 edges. Pikhurko then applied the stability method — "an ingenious combination of Sidorenko's argument with the stability method" (Keevash survey, §9) — to upgrade this to an exact, unique-extremizer result for large $n$: the Turán construction is the unique largest such 3-graph. - The diagnostic failure mode: instability blocks the method entirely. The full (unrestricted) tetrahedron problem $\pi(K_4^{(3)})$ (Erdős #500 — Turán density of the tetrahedron $K_4^{3}$) is believed not stable: Brown, Kostochka, Fon-der-Flaass, and Frohmader each exhibit pairwise non-isomorphic 3-graph constructions all achieving the conjectured extremal density $5/9$ (cited in Keevash's survey, p.19, and this wiki's problems/500.md). Because the extremal example is not unique, there is no single structure for near-extremal graphs to be "close to," so the stability method has no foothold — widely believed to be *why* flag-algebra/SDP methods have stalled on this exact problem since 2010–2011, in contrast to their success on the *restricted* sub-case above where stability does hold. - Escaping instability by changing the norm. Balogh–Clemen–Lidický (arXiv:2108.10408, 2022) and Bodnár–Chen–Deng et al. (arXiv:2511.12506, 2025) show that reformulating the tetrahedron problem in the $\ell_2$ (codegree-squared-sum) norm rather than the classical $\ell_1$ (raw edge count) norm *restores* stability and uniqueness — the 2025 uniqueness paper explicitly builds an "enhanced Simonovits stability" argument via local bad-edge/missing-edge swap lemmas, using Pikhurko's $\ell_1$-restricted stability result as one ingredient (this wiki's solved/tetrahedron-l2-norm.md). This is direct evidence that "no stability in this exact formulation" is a fact about the *chosen density measure*, not an immovable fact about the underlying combinatorial object — a live recombination move when a stability attack stalls.

WHEN it applies

you already have (or can obtain by an independent method — flag algebras, the Lagrangian/hypergraph-Lagrangian method, entropy, KST-style double counting, an averaging/symmetrization argument) an asymptotic extremal bound $\mathrm{ex}(n,\mathcal L)=(c+o(1))\binom n2$ (or the hypergraph density $\pi$), together with a conjectured (or provable) essentially-unique extremal construction. It is the standard second step whenever a problem's headline difficulty is "pin down the *exact* constant / characterize the *unique* extremizer for large $n$," not merely the asymptotic order. It typically does not apply, or requires first modifying the problem (different norm, restricted sub-family, added local condition), when multiple structurally different constructions are known to achieve the same asymptotic extremum (the Erdős #500 — Turán density of the tetrahedron $K_4^{3}$ tetrahedron obstruction above is the canonical warning sign).

WHY it works (the mechanism)

the classical proof (Füredi's route) reduces to one clean combinatorial fact — Theorem 1 above — that a $K_{p+1}$-free graph $t$ edges short of the Turán number always contains a $p$-chromatic subgraph missing only $t$ of its own edges; proved by a short direct argument (find, greedily/inductively, a partition realizing an at-most-$p$-chromatic subgraph of near-maximal size, using $K_{p+1}$-freeness only to bound how far the graph can be from $p$-partite). This "no-$\varepsilon$" statement is then bootstrapped to the general family $\mathcal L$ via one application of Szemerédi's regularity lemma: regularize $G$, note the *reduced graph* (weighted by regularity-cluster densities) inherits an approximate $K_{p+1}$-freeness-like property from $\mathcal L$-freeness of $G$ (since a clique of dense regular pairs in the reduced graph, by the regularity/embedding lemma, would embed a member of $\mathcal L$ into $G$), apply Theorem 1 to the reduced graph, then pull the resulting near-$p$-partite structure back up through the regularity partition — the $\varepsilon n^2$ slack in the stability theorem is exactly absorbing the regularity lemma's own approximation error. In the analytic (Pikhurko) route the same idea is recast as: the graphon limit of any extremal sequence must itself be $p$-partite by a continuous/measure-theoretic version of Zykov symmetrization, and $\delta_2$-compactness of graphon space converts "the limit is unique" into "all sufficiently extremal finite graphs are uniformly close to it."

Downstream use — how a solver actually deploys the stability method to prove a NEW exact result (the two-stage recipe, per Keevash's survey): 1. Stage 0 (prerequisite). Establish or cite an asymptotic bound $e(G)\le(c+o(1))N$ for the relevant extremal problem, with a conjectured unique extremal construction $\mathcal E$. (Tools that typically supply this: Erdős–Stone–Simonovits / Turán-type theorems, Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s})-style double counting, flag algebras, the hypergraph Lagrangian method, or an entropy argument.) 2. Stage 1 — prove stability. Show any $\mathcal L$-free (or $F$-free) $G$ with $e(G)\ge(c-\delta)N$ can be edited by $\le\varepsilon N$ edges into a copy of $\mathcal E$. Routes: (a) the regularity-lemma bridge above, when a regularity/counting lemma is available for the host structure; (b) directly, via supersaturation + the removal lemma, when $\pi(\mathcal L)$ is already known and the graphs in question are hypergraphs of a special "expanded"/derived shape (Keevash's $F^{(t)}$ mechanism above); (c) Pikhurko's analytic graphon/graphit route when neither of the above is tractable. 3. Stage 2 — bootstrap stability into an exact result via a "defect" / local-perturbation argument. Treat any hypothetical better-than-$\mathcal E$ construction as $\mathcal E$ plus a bounded number of "imperfections" (bad edges/missing edges/misplaced vertices), then show *directly* (no asymptotics needed at this stage — this is usually the easier, purely local half) that every possible imperfection can only *decrease* the edge count relative to perfect $\mathcal E$ — following the four-step template in Facts: push to high minimum degree, fix an optimal partition, show few bad-degree vertices, show zero bad edges survive. This stage is what actually produces the exact/unique-extremizer conclusion, not Stage 1 alone. 4. Recognize the AES-variant shortcut. Sometimes Stage 1+2 collapse into a single clean minimum-degree threshold statement with no $\varepsilon,\delta$ at all (the Andrásfai–Erdős–Sós pattern: "min degree above threshold $\Rightarrow$ exactly $\mathcal E$-shaped, not just close"). When available, this is strictly stronger and easier to apply downstream than the $\varepsilon$-form — check for it before running the full asymptotic-stability machinery. 5. Before investing in Stage 1, sanity-check uniqueness. If independent constructions of non-isomorphic near-extremal examples are already known or suspected (as with Erdős #500 — Turán density of the tetrahedron $K_4^{3}$), stability is likely false in the current formulation and Stage 1 will not go through — the productive move is then to either restrict to a sub-family where uniqueness is restored (Pikhurko's "no 4-set with 1 or 4 edges" restriction) or change the measured quantity/norm entirely (the $\ell_1\to\ell_2$ pivot of 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)) rather than attacking the original formulation head-on.

Related

- Turán number ex(n,H): extremal edge-count for forbidden subgraphs — the general $\mathrm{ex}(n,H)$ framework this method upgrades from asymptotic to exact; already states the stability theorem informally as tool #5 in its own recombination recipe. - Supersaturation theorem — density strictly above the Turán threshold forces Ω(n^h) copies, not just one (Erdős–Simonovits 1983) — supplies the "excess density $\Rightarrow$ many copies" input that, combined with the removal lemma, gives one of the two general routes to proving stability for hypergraph families. - 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 — the Szemerédi-regularity/removal-lemma machinery underlying both Füredi's regularity-based reproof of the classical stability theorem and the supersaturation+removal-lemma route to hypergraph stability. - Kővári–Sós–Turán theorem: the double-counting bound ex(n,K_{s,t}) = O(n^{2-1/s}) — a Stage-0 asymptotic-bound tool (double counting + convexity) that stability-method proofs often start from before attempting a structural upgrade. - Erdős #500 — Turán density of the tetrahedron $K_4^{3}$ — the tetrahedron problem $\pi(K_4^{(3)})$: the canonical example where the stability method is believed to structurally *fail* (many non-isomorphic near-extremal constructions), explaining 15+ years of flag-algebra stagnation; contrasted with Pikhurko's successful stability-based exact result on a restricted sub-case. - Erdős #712 — Turán density of complete $r$-uniform hypergraphs $K_k^r$ — the general $\pi(K_k^{(r)})$ Turán-density family; instability is conjectured to be the core obstruction across the whole family, not just $K_4^{(3)}$/$K_5^{(3)}$. - 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 $\ell_2$-norm reformulation of the tetrahedron problem that *restores* stability and yields an exact, unique-extremizer result via "enhanced Simonovits stability" (local swap lemmas), the concrete case study for the "change the norm to escape instability" recombination move.