极值图中的超饱和 | Codeboy's Blog

形式陈述

设 $H$ 是含 $h$ 个顶点且至少有一条边的固定简单图，并令

\pi(H)=\lim_{n\to\infty} \frac{\operatorname{ex}(n,H)}{\binom n2}.

Erdős–Simonovits 超饱和定理断言：对每个 $\eta>0$ ，存在 $c=c(H,\eta)>0$ 与 $n_0=n_0(H,\eta)$ ，使得每个 $n\ge n_0$ 且

e(G)\ge\bigl(\pi(H)+\eta\bigr)\binom n2

的图 $G$ 至少含 $c n^h$ 个 $H$ 的副本。若按单射同态计数，常数会乘上 $|\operatorname{Aut}(H)|$ ；定理的幂次与“正比例”结论不变。等价的常用写法以极值数为基线：若 $e(G)\ge\operatorname{ex}(n,H)+\eta n^2$ ，则同样有 $\Omega_{H,\eta}(n^h)$ 个副本。

量词次序不可颠倒：先固定 $H$ 和密度余量 $\eta$ ，才得到不依赖 $n$ 的正数 $c$ ；随后结论对所有充分大的 $n$ 成立。若 $\eta=\eta(n)\to0$ ，常数也可能随之消失，不能从定理直接保留统一的 $c$ 。

直觉

极值定理只说越过门槛后至少出现一次禁图，超饱和则说固定比例的越界不可能集中在少数局部事故里。随机抽取一个固定大小的顶点集时，它仍以正概率继承过高的边密度，因而其中必须出现 $H$ 。每个具体 $H$ 副本会被许多抽样集合重复看见；把两边的计数相除，就得到与全部 $h$ 元顶点组同阶的副本数。

这也解释了 $n^h$ 的幂次为何正确：一个 $h$ 顶点图在 $n$ 点宿主中至多有常数乘 $n^h$ 个位置，定理证明固定密度余量已经迫使其中正比例的位置成功。它不是声称副本彼此边不交，更不保证它们均匀散布在每个顶点附近。

证明机制

取足够大的固定整数 $m$ ，使 $\operatorname{ex}(m,H)/\binom m2<\pi(H)+\eta/2$ 。从 $G$ 均匀抽取 $m$ 点诱导子图 $G[S]$ ，有

\mathbb E e(G[S]) =e(G)\frac{\binom m2}{\binom n2} \ge(\pi(H)+\eta)\binom m2.

边数至多为 $\binom m2$ ，所以不能只有趋近于零比例的 $S$ 超过 $\operatorname{ex}(m,H)$ ；否则期望达不到上述固定余量。每个这样的 $S$ 含一个 $H$ ，而一个 $H$ 副本恰被 $\binom{n-h}{m-h}$ 个 $m$ 集包含。这个随机抽样与双重计数给出 $c\binom nh$ 级别的下界。

例子与边界

从偶数阶的 $T_2(n)=K_{n/2,n/2}$ 出发，在一侧加入一条内部边 $uv$ 。新图刚比 $\operatorname{ex}(n,K_3)=n^2/4$ 多一条边； $uv$ 与另一侧的每个顶点组成三角形，所以恰新增 $n/2$ 个三角形。取 $n=6$ 时， $K_{3,3}$ 的 $9$ 条边加一条部内边，正好得到 $3$ 个三角形，可以逐个列为 $uvx$ ，其中 $x$ 遍历另一部。

这个例子同时标出定理边界：只多一条边时有 $\Theta(n)$ 个三角形，而不是 $\Theta(n^3)$ 。若在同一部加入 $\eta n^2$ 条边，每条内部边与约 $n/2$ 个对侧顶点配对，才自然积累出 $\Theta(\eta n^3)$ 个三角形。固定密度余量不能削成“至少多一边”。

副本计数还依赖约定。若 $H=K_3$ ，无标号三角形数与标号嵌入数相差 $6$ ；若要求诱导副本，新增宿主边可能破坏原有诱导副本，普通超饱和定理不能直接套用。对超图存在对应版本，但极值密度和常数的确定往往更困难。

推论与应用

超饱和把Turán 型存在结论升级为计数结论，是图移除引理逆向直觉的重要来源：若删除少量边仍无法消灭所有 $H$ ，图中就应有大量 $H$ 副本。它也为随机抽样、稀疏化和容器方法提供“坏集合很多”的定量输入。

在性质测试中，若一个稠密图距离 $H$ -free 性质很远，随机采常数个顶点便有常数概率看见 $H$ ；超饱和与移除思想解释了为何查询复杂度可以不随 $n$ 增长。更精细的 supersaturation 问题会在只比 $\operatorname{ex}(n,H)$ 多 $q=o(n^2)$ 条边时求最少副本数，此时答案依赖极值构造的局部形状，不能由上面的固定密度版本代替。

参考资料

Paul Erdős and Miklós Simonovits, “Supersaturated graphs and hypergraphs,” Combinatorica 3 (1983), 181–192.
Béla Bollobás, Extremal Graph Theory, Academic Press, 1978, Chapter VI.
Yufei Zhao, Graph Theory and Additive Combinatorics: Exploring Structure and Randomness, Cambridge University Press, 2023, Section 1.3.

形式陈述 ​

证明机制 ​

反向链接

形式陈述

证明机制