2026-07-24 · 从禁三角形到密度阈值

0. 导读与元结构 (Orientation & Meta-structure)

起点问题。 给定 $n$ 个顶点，如果禁止出现三角形，还能保留多少条边？这不是在一个既定图中“找三角形”，而是在所有满足禁形条件的图之间做最大化。局部条件 $K_3⊈G$ 如何约束全局密度，正是 extremal graph theory（极值图论）的原型问题。

对象与量词层。 今天固定正整数 $n$，遍历所有有限、无向、无自环、无重边的 simple graphs（简单图）$G=(V,E)$，其中 $|V|=n$；对每一条边 $uv\in E$，检查端点邻域；最后在所有 $K_3$-free 图之间最大化 $|E|$。这里的 “$K_3$-free” 指不含 $K_3$ 作为普通子图，不是“不含诱导三角形”。

预备知识。 顶点度数 $d(v)$、邻域 $N(v)$、握手引理

$$\sum _{v\in V}d(v)=2|E|,$$

以及 Cauchy–Schwarz inequality（Cauchy–Schwarz 不等式）。

主证明引擎。 禁三角形迫使每条边的两个端点没有共同邻点；把这一局部事实对全部边求和，得到度平方的上界，再用 Cauchy–Schwarz 从另一侧压住度平方。极值结构则由“每一步何时取等”读出。

位置。 今天是 Friday，也是 roaming-2026-w30-extremal-density 的 Day 1/1：从组合优化进入概率法习题，再由色数走向渐近密度，完成本周一次跨域 roaming issue。主线可由上本科图论进入；graduate / modern extension 会抵达 stability（稳定性）、graph limits（图极限）与 Erdős–Stone–Simonovits 定理。

1. 核心概念、定理与谱系 (Concept, Theorem & Lineage)

1.1 从“禁止什么”定义“最多多少”

定义（extremal number / Turán number，极值数 / Turán 数）。 设 $H$ 是一个固定有限简单图。对每个正整数 $n$，定义

$$\mathrm{ex}(n,H):=max\{|E(G)|:G\text{ 是简单图},|V(G)|=n,H⊈G\}.$$

完整地说：对每个固定 $H$ 与每个 $n\ge 1$，在全部 $n$ 顶点简单图 $G$ 中，只保留不存在单射 $\phi :V(H)\to V(G)$ 使

$$\mathrm{\forall }xy\in E(H),\phi (x)\phi (y)\in E(G)$$

的那些图，再取边数最大值。映射不要求把 $H$ 的非边送到 $G$ 的非边，所以这里禁止的是普通子图。

1.2 Mantel 定理：三角形的精确阈值

定理（Mantel's theorem，Mantel 定理）。 对每个整数 $n\ge 1$，若 $G=(V,E)$ 是 $n$ 顶点简单无向图，并且

$$\mathrm{\forall }x,y,z\in V\text{ 两两不同},\{xy,xz,yz\}⊈E,$$

即 $G$ 不含三角形，则

$$|E|\le \lfloor \frac{n^2}{4}\rfloor .$$

而平衡完全二部图

$$K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }$$

无三角形且恰有 $\lfloor n^2/4\rfloor$ 条边。因此

$$\mathrm{ex}(n,K_3)=\lfloor \frac{n^2}{4}\rfloor .$$

证明。 记 $m=|E|$。若 $m=0$，结论显然。以下设 $m>0$。

对每条边 $uv\in E$，$u$ 与 $v$ 不能有共同邻点；否则共同邻点 $w$ 会使 $u,v,w$ 构成三角形。因此

$$N(u)\cap N(v)=\varnothing ,d(u)+d(v)\le n.$$

对所有边求和：

$$\sum _{uv\in E}(d(u)+d(v))\le mn.$$

左边每个 $d(v)$ 被与 $v$ 关联的每条边各计一次，总共出现 $d(v)$ 次，故

$$\sum _{uv\in E}(d(u)+d(v))=\sum _{v\in V}d(v{)}^2.$$

另一方面，由 Cauchy–Schwarz 与握手引理，

$$\sum _{v\in V}d(v{)}^2\ge \frac{1}{n}{(\sum _{v\in V}d(v))}^2=\frac{(2m{)}^2}{n}.$$

合并两侧得到

$$\frac{4m^2}{n}\le mn.$$

因为 $m>0$，可约去 $m$，于是 $m\le n^2/4$；$m$ 为整数，故

$$m\le \lfloor \frac{n^2}{4}\rfloor .$$

最后，把顶点分成大小分别为 $\lfloor n/2\rfloor$ 与 $\lceil n/2\rceil$ 的两部，只连接异部顶点。任何三点中至少两点同部，而同部无边，所以不可能构成三角形；边数为

$$\lfloor \frac{n}{2}\rfloor \lceil \frac{n}{2}\rceil =\lfloor \frac{n^2}{4}\rfloor .$$

上下界相合，定理得证。

1.3 为什么极值图必须是平衡完全二部图

Mantel 定理还有唯一性：达到最大边数的图必同构于 $K_{\lfloor n/2\rfloor ,\lceil n/2\rceil }$。其机制可由另一条不等式链直接看出。

取最大度顶点 $v$，令

$$A=N(v),B=V\setminus A.$$

因为图无三角形，$A$ 是独立集；又因 $d(v)=|A|$ 是最大度，所有 $x\in B$ 都满足 $d(x)\le |A|$。于是

$$m\le \sum _{x\in B}d(x)\le |A||B|\le \lfloor \frac{n^2}{4}\rfloor .$$

若首尾相等，则第一步取等迫使 $B$ 内无边，第二步取等迫使每个 $x\in B$ 与 $A$ 的所有顶点相邻，第三步取等迫使 $|A|$ 与 $|B|$ 相差至多 $1$。故 $G$ 正是平衡完全二部图。

这说明极值证明不只回答“最多多少”，还编码了“唯一结构为何如此”。

1.4 谱系：Mantel → Turán → 色数控制密度

Yufei Zhao 的教材把这条谱系表述得很清楚：[1]

1. Mantel 在 1907 年解决禁三角形问题，它通常被视为极值图论的起点。
2. Turán theorem（Turán 定理，1941）把三角形推广到团：对固定 $r\ge 1$，所有 $n$ 顶点 $K_{r+1}$-free 图中，唯一边数最大者是各部大小相差至多 $1$ 的完全 $r$-部图 $T_{n,r}$。
3. 对任意固定且至少含一条边的图 $H$，Erdős–Stone–Simonovits theorem 给出渐近结论

$$\underset{n\to \mathrm{\infty }}{lim}\frac{\mathrm{ex}(n,H)}{(\genfrac{}{}{0ex}{}{n}{2})}=1-\frac{1}{\chi (H)-1},$$

其中 $\chi (H)$ 是 chromatic number（色数）。等价的完整量词形式是：

$$\mathrm{\forall }\epsilon >0,\mathrm{\exists }{n}_0=n_0(H,\epsilon ),\mathrm{\forall }n\ge n_0,|\frac{\mathrm{ex}(n,H)}{(\genfrac{}{}{0ex}{}{n}{2})}-(1-\frac{1}{\chi (H)-1})|<\epsilon .$$

Graduate / modern extension. 精确的低阶项仍会记住 $H$ 的细节，但二次主项只看 $\chi (H)$。特别地，若 $H$ 是二部图，则 $\chi (H)=2$，上式只给出 $\mathrm{ex}(n,H)=o(n^2)$；它没有告诉我们真正的增长阶。这正是现代极值组合中“已知密度、未知尺度”的重要分界。另一方面，若一个无三角形图的边数接近 $n^2/4$，stability theory（稳定性理论）会进一步说明它的结构也必须接近平衡二部图。

2. 固定模板习题 (Template Exercise)

题目

设 $G=(V,E)$ 是任意有限简单图，$|E|=m$。证明：存在一个顶点划分

$$V=A\bigsqcup B$$

使至少 $m/2$ 条边横跨 $A$ 与 $B$。等价地，$G$ 含有一个至少有 $\lceil m/2\rceil$ 条边的 spanning bipartite subgraph（生成二部子图）。

模板识别

看到“证明存在一个划分 / 构造，使某个总量至少达到某个比例”，可尝试 probabilistic method（概率方法）：随机生成候选对象，把总量写成指标变量之和，算期望，再用“最大值不小于平均值”得到确定性存在。

分级提示

1. Hint 1. 独立地以概率 $1/2$ 把每个顶点放入 $A$ 或 $B$。
2. Hint 2. 对每条边 $e=uv$ 定义指标 $X_e$：当 $u,v$ 落在不同部时取 $1$，否则取 $0$。
3. Hint 3. 先计算单条边满足 $X_e=1$ 的概率，再对 $X=\sum _{e\in E}{X}_e$ 使用期望的线性性；不需要假设不同 $X_e$ 独立。
4. Hint 4. 如果每个划分的跨边数都严格小于期望，会发生什么矛盾？

3. 大家之言 (Mathematician in Their Own Words)

可核验语境。 David Hilbert 在 1900 年巴黎 International Congress of Mathematicians（国际数学家大会）发表 Mathematical Problems 演讲。Mary Winston Newson 经作者许可所作英译发表于 1902 年 7 月的 Bulletin of the American Mathematical Society；Project Euclid 给出的书目信息为卷 8、第 10 期、437–479 页。[2] 下句位于印刷页 438：

“It is by the solution of problems that the investigator tests the temper of his steel ; he finds new methods and new outlooks, and gains a wider and freer horizon.”

中译。 “研究者正是在解决问题时检验自己的锋刃；他由此发现新的方法与新的视角，并获得更广阔、更自由的地平线。”

评论。 这不是把“刷题”浪漫化。Hilbert 紧接着讨论的是：一个好问题的价值往往要由它给数学带来的方法增益来判断。Mantel 问题恰是小而硬的例子——问题陈述只涉及三角形和边数，解决它却自然逼出邻域分离、边上度数求和、Cauchy–Schwarz、极值取等、symmetrization（对称化）与 stability 等一整组可迁移机制。

所以，问题的尺度与方法的尺度并不相同。一个可由本科知识进入的问题，也可能成为通向现代结构理论的窄门。

4. 反例与边界 (Counterexample & Boundary)

把“无三角形”弱化成“无 $K_4$”，$n^2/4$ 立即失效

令

$$G=K_{2,2,2},$$

即把六个顶点分成三个大小均为 $2$ 的独立集 $A,B,C$，连接所有异部顶点。

逐项检查：

1. 顶点数。 三部各有 $2$ 点，所以 $|V(G)|=6$。
2. 边数。 每一对部之间有 $2\cdot 2=4$ 条边，共有三对部，因此
   $$|E(G)|=3\cdot 4=12.$$
3. 它确实不含 $K_4$。 同一部内没有边，所以一个 clique（团）至多从每部取一个顶点；这里只有三部，故团大小至多为 $3$。
4. 但它含三角形。 从 $A,B,C$ 各取一个顶点，三条异部边全部存在。
5. Mantel 上界已被突破。 六顶点时
   $$\lfloor \frac{6^2}{4}\rfloor =9,$$
   而 $12>9$。

因此，不能把 Mantel 定理的假设从“$K_3$-free”随意换成更弱的“$K_4$-free”。正确替代不是保留同一个常数，而是进入 Turán 定理：禁 $K_4$ 的极值结构是平衡完全三部图，二次主项约为 $n^2/3$。这也预示了 Erdős–Stone–Simonovits 定理为何由被禁图的色数决定密度常数。

5. 今日一问与数学地图 (Question & Map)

今日一问（Mantel stability，Mantel 稳定性）。 设 $k\ge 0$ 为整数，$G$ 是 $n$ 顶点无三角形图，并满足

$$|E(G)|\ge \lfloor \frac{n^2}{4}\rfloor -k.$$

证明：从 $G$ 中删除至多 $k$ 条边，就能得到一个二部图。

这比 Mantel 定理更强：它不仅说边数不能超过阈值，还说只要边数距离阈值不远，图的结构就距离二部图不远。

定向提示。 重新使用第 1.3 节的最大度顶点 $v$ 与分割

$$A=N(v),B=V\setminus A.$$

$A$ 已经是独立集。不要重证整个 Mantel 定理；请追踪不等式链中的“亏损”究竟能控制 $B$ 内多少条边。

数学地图。

$$\begin{array}{c}\text{简单图、度数、邻域}\\ \Downarrow \\ \text{禁局部子图 }H\\ \Downarrow \\ \mathrm{ex}(n,H)\text{ 与 Mantel 精确界}\\ \Downarrow \\ \text{Turán 多部极值结构}\\ \Downarrow \\ \text{stability：近极值迫使近结构}\\ \Downarrow \\ \text{supersaturation 与 graph removal}\\ \Downarrow \\ \text{Erdős--Stone--Simonovits 色数密度}\\ \Downarrow \\ \text{graphons、随机图与稠密图极限}\end{array}$$

这里有两条相邻路线：概率方法问“随机对象为何以正概率具有好结构”，极值图论问“坏结构被禁止后密度最多多大”。二者在随机割、supersaturation（超饱和）与随机图阈值处重新汇合。

附录 A：习题完整解答 (Full Solution)

展开完整解答

可复用模板：随机生成候选对象 $\to$ 指标变量分解总量 $\to$ 线性期望 $\to$ 用平均值推出确定性存在。

令样本空间为所有二染色

$$\mathrm{\Omega }=\{0,1{\}}^V,$$

并给每个染色相同概率。把颜色为 $0$ 的顶点放入 $A$，颜色为 $1$ 的顶点放入 $B$；等价地，各顶点独立且以概率 $1/2$ 进入任一部。

对每条边 $e=uv\in E$，定义

$$X_e=\{\begin{array}{ll}1,& u,v\text{ 落在不同部},\\ 0,& u,v\text{ 落在同一部}.\end{array}$$

四种有序颜色对 $(0,0),(0,1),(1,0),(1,1)$ 等可能，其中两种异色，所以

$$\mathbb{P}(X_e=1)=\frac{1}{2},\mathbb{E}[X_e]=\frac{1}{2}.$$

令

$$X=\sum _{e\in E}{X}_e.$$

则 $X$ 正是该随机划分的跨边数。由期望的线性性，

$$\mathbb{E}[X]=\sum _{e\in E}\mathbb{E}[X_e]=\frac{m}{2}.$$

这里不需要各 $X_e$ 相互独立；共享端点的边所对应的指标可能相关，但线性期望对相关变量仍成立。

因为有限样本空间上的最大值不小于平均值，所以至少存在一个具体划分满足

$$X\ge \mathbb{E}[X]=\frac{m}{2}.$$

又因 $X$ 是整数，实际有

$$X\ge \lceil \frac{m}{2}\rceil .$$

保留这些跨边并删除同部边，就得到一个以 $(A,B)$ 为二部划分、至少含 $\lceil m/2\rceil$ 条边的生成二部子图。

资料与来源 (Sources)

1. Yufei Zhao, Graph Theory and Additive Combinatorics: Exploring Structure and Randomness, Cambridge University Press, 2023. 作者公开书稿的 Chapter 1 “Forbidding a Subgraph” 用于核验 $\mathrm{ex}(n,H)$ 的定义、Mantel 定理的两种证明及唯一取等情形、Turán 定理、stability exercise 与 Erdős–Stone–Simonovits 定理：书稿主页 https://yufeizhao.com/gtacbook/ ；本期实际读取的 Chapter 1 PDF https://yufeizhao.com/gtacbook/1.pdf 。
2. David Hilbert, “Mathematical Problems,” lecture delivered before the International Congress of Mathematicians at Paris in 1900, translated with the author's permission by Mary Winston Newson, Bulletin of the American Mathematical Society 8(10), July 1902, 437–479. 第 3 节引文核对于印刷页 438。Project Euclid 书目页与全文入口：https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society/volume-8/issue-10/Mathematical-problems/bams/1183417035.full ；AMS PDF：https://www.ams.org/journals/bull/1902-08-10/S0002-9904-1902-00923-3/S0002-9904-1902-00923-3.pdf 。