极值组合学中的稳定性方法

一个上界证明若由一串不等式组成，接近最终等号通常迫使每一步都接近等号。稳定性方法系统地追踪这些亏损：度数不均、错误的部内边、缺失的跨部边各消耗多少目标值；当总亏损很小，所有结构缺陷便不能同时很大。

常见证明路线先用Erdős–Stone 定理公理库Erdős–Stone 定理Erdős–Stone theorem · Erdős–Stone–Simonovits theorem · 厄多斯–斯通定理固定禁图的色数决定其极值数的二次主项，而不决定低阶误差与精确取等结构。排除过大的非 $r$ 部核心，再清理少数异常顶点，最后用Turán 定理公理库Turán 定理Turán's theorem · 图兰定理不含给定大团的有限简单图以均衡完全多部图为唯一的边数极大者。或其证明中的均衡不等式控制各部。方法的产物不是一个新极值值，而是一张“近取等者必须聚集在哪里”的地图；这张地图随后常把渐近结果升级为精确结果。

工作步骤 ​

首先选定能表示候选极值族的距离，图中通常取边集对称差 $|E(G)\mathrm{△}E(T)|$。其次找一条带有亏损项的上界，而不只保留粗略的 $e(G)\le t_r(n)$。再次从小亏损推出分部、度数或邻域的一致性。最后处理少数异常对象：若某种局部缺陷仍存在，就用交换操作构造更多边而不产生禁图，或证明它迫使禁图出现。

完全二分图 $K_{a,n-a}$ 无三角形，边数可写成

因此若它距 Mantel 上界至多 $\delta n^2$，就有 $|a-n/2|\le \sqrt{\delta }n$。这是稳定性推理的可计算缩影：目标值的二次亏损直接控制划分的不平衡。比如 $n=100$、边数至少 $2500-25$ 时，部大小只能相差至多 $10$；并非任何完全二分图都算“接近均衡”。

稳定性不等于唯一性。可从 $K_{n/2,n/2}$ 删除任意 $o(n^2)$ 条跨部边，得到大量互不同构的近极值无三角形图；它们都离 Turán 图很近，却没有一个必须与之相同。稳定性也通常使用全局编辑距离：允许 $o(n)$ 个顶点各带 $\mathrm{\Theta }(n)$ 条错误边，所以不能自动推出每个顶点的度或邻域都接近模板。若需要逐顶点结论，必须另做清理或假设最小度下界。

另一个边界是极值族可能不唯一。此时应证明对象接近“某个”取等构造，或接近若干模板的并集；强行选定单一模板会把真实的相变或多相结构抹掉。对稀疏尺度 $\mathrm{ex}(n,H)=o(n^2)$，用 $\epsilon n^2$ 衡量误差可能过粗，还需按问题的自然边数尺度重新归一化。

一旦得到稳定性，常可检查有限种局部异常，把“$o(n^2)$ 接近”提升为充分大 $n$ 上的精确取等定理。稳定性也是枚举近极值图、分析随机禁图模型和建立鲁棒算法的基础：先恢复近似分部，再在小误差集合上做精确处理。

它与超饱和公理库极值图中的超饱和Supersaturation in extremal graphs · Erdős–Simonovits supersaturation theorem · 超饱和定理图的边密度固定超过禁图极值密度时，禁图副本数必从一个跃升到顶点数的正确幂次量级。互补。稳定性描述阈值下方的近取等者，超饱和描述越过阈值后的副本爆发；两者合用时，可将远离所有模板的图证明为必然含有许多禁用配置。移除引理公理库图移除引理Graph removal lemma · H-removal lemma · 图删除引理固定图的副本数若低于正确幂次的足够小比例，就能删除少量边消灭全部该图副本。也采用类似的距离语言，但其假设是副本稀少、结论是可少量删边，逻辑方向与稳定性并不相同。