2. Turán 定理: 禁止团

受定理 1.0.2 的启发, 我们转向以下更一般性的问题.

问题 2.1. 不包含 $K_{r+1}$ ($K_{r+1}$-free, 这里 $K_{r+1}$ 是指 $r+1$ 个点的团) 的 $n$ 个点的图中, 最多能有多少条边?

扩展之前的二分图 (二部图) 结构, 我们容易看到 $r$ 部图不包含 $K_{r+1}$.

定义 2.2. 我们定义 Turán 图 $T_{n,r}$ 是 $n$ 个顶点的完全 $r$ 部图, 其中每个部分的顶点数都为 $\lfloor \frac{n}{r}\rfloor$ 或 $\lceil \frac{n}{r}\rceil$.

(...) Turán 图 $T_{10,3}$

在本节我们将证明 $T_{n,r}$ 确实最大化了 $K_{r+1}$-free 图中的边数:

定理 2.3 (Turán). 如果 $G$ 是 $n$ 个顶点的 $K_{r+1}$-free 图, 则 $e(G)\le$ $e\left(T_{n,r}\right)$.

当 $r=2$ 时, 这就是定理 1.0.2. 我们现在给出定理 2.3 的三个证明, 其中前两个与 Mantel 定理 (定理 1.0.2) 的证明思路相同.

版本 1. 固定 $r$, 我们对 $n$ 进行归纳. 注意到如果 $n\le r$, 命题是不言自明的 (因为 $K_n$ 是 $K_{r+1}$-free 的) . 现在我们假设 $n>r$ 并且 Turán 定理对于所有少于 $n$ 个顶点的图都成立. 令 $G$ 是一个 $n$ 个顶点的 $K_{r+1}$-free 图, 并且具有尽可能最多的边数. 请注意, $G$ 必须包含子图 $K_r$ , 否则我们可以在 $G$ 中添加任意一条边使其仍然是 $K_{r+1}$-free 的. 令 $A$ 是 $G$ 中 $r$-clique (大小为 $r$ 的团) 的顶点集, 令 $B:=V\backslash A$. 由于 $G$ 是 $K_{r+1}$-free 的, 每个 $v\in B$ 在 $A$ 中至多有 $r-1$ 个邻点. 所以$$\begin{array}{rl}e(G)& \le \left(\genfrac{}{}{0ex}{}{r}{2}\right)+(r-1)|B|+e(B)\\ & \le \left(\genfrac{}{}{0ex}{}{r}{2}\right)+(r-1)(n-r)+e\left(T_{n-r,r}\right)\\ & =e\left(T_{n,r}\right)\end{array}$$第一个不等式来自计算 $A、B$ 的边以及它们之间的所有边的数量. 第二个不等式来自归纳假设. 最后一个等式成立是因为如果从 $T_{n,r}$ 的 $r$ 个部分中每个删去一个顶点, 总共将会删去和这些点相连的 $\left(\genfrac{}{}{0ex}{}{r}{2}\right)+(r-1)(n-r)$ 条边.

$\square$

版本 2, Zykov symmetrization.

和之前一样, 令 $G$ 是一个 $n$ 个顶点, $K_{r+1}$-free 且尽可能边数最大的图. 我们断言 $G$ 的 “非边” 形成等价关系: 也就是说, 如果 $xy,yz\notin E$, 那么 $xz\notin E$. 对称性和自反性很容易检验. 为了检查传递性, 考虑反面, 假设存在 $x,y,z\in V$ 其中 $xy,yz\notin E$ 但 $xz\in E$.

如果 $d(y)<d(x)$, 我们可以用 $x$ 的 “克隆” 替换 $y$. 也就是说, 我们删除 $y$ 并添加一个新顶点 $x^{\prime }$, 它的邻点集正好是 $x$ 的邻点集 (并且 $x$ 和 $x^{\prime }$ 之间没有边) , 如下图.

(...) $x$ 和它的 “克隆” $x^{\prime }$

显然, 替换后得到的图 $G^{\prime }$ 也是 $K_{r+1}$-free 的. 另一方面, (因为 $xy\notin E$) $G^{\prime }$ 比 $G$ 有更多的边, 这与 $G$ 的边数尽可能最大的前提矛盾.

因此, 对于所有的 $xy\notin E$, 我们有 $d(y)\ge d(x)$. 类似地, 因为 $yz\notin E$, 我们有 $d(y)\ge d(z)$. 现在, 用 $y$ 的 “克隆” 替换 $x$ 和 $z$ 得到新的图 $G^{\prime }$ 是 $K_{r+1}$-free 的 (因为 $y$ 不在任何子图 $K_{r+1}$ 中) . 而且有$$e\left(G^{\prime }\right)=e(G)-(d(x)+d(z)-1)+2d(y)>e(G)$$与 $e(G)$ 是最大值相矛盾. 因此这样的三元组 $(x,y,z)$ 在 $G$ 中不存在, 传递性成立.

这种等价关系表明 $G$ 的补集是由若干个团组成的. 因此 $G$ 是一个完全多部图, 从而最多包含 $r$ 个部分. 容易验证, 增加部的数量会增加 $G$ 中的边数. 类似地, 如果两个部分的顶点数相差超过 1, 将一个顶点从较大部分移动到较小部分会增加 $G$ 中的边数. 由此可知, 达到最大边数的图为 $T_{n,r}$ .

$\square$

我们的第三个也是最后一个证明使用了一种叫做概率方法 (probabilistic method) 的技术. 在这种方法中, 人们以一种巧妙的方式将随机性引入确定性问题来得到一个确定性的结果.

版本 3. 令 $G=(V,E)$ 是一个 $n$ 顶点的 $K_{r+1}$-free 图. 考虑一个均匀随机的顶点排列 $\sigma$. 令$$X=\{v\in V:v\text{与}\sigma \text{中所有早于}v\text{出现的顶点相邻}\}.$$

观察到 $X$ 中的顶点集形成一个团. 由于排列是均匀随机选择的, 我们有$$\mathbb{P}(v\in X)=\mathbb{P}(v\text{ 出现在其所有不相邻顶点之前 })=\frac{1}{n-d(v)}.$$所以, $$r\ge \mathbb{E}[|X|]=\sum _{v\in V}\mathbb{P}(v\in X)=\sum _{v\in V}\frac{1}{n-d(v)}\stackrel{\text{凸性}}{\ge }\frac{n}{n-2m/n}.$$整理得到 $m\le \left(1-\frac{1}{r}\right)\frac{n^2}{2}$ (一个已经适用于大多数情况的的上界) . 请注意, 当 $n$ 可以被 $r$ 整除时, 这个不等式立即给出了 Turán 定理的证明. 当 $n$ 不能被 $r$ 整除时, 我们需要借助凸性做更多的工作来论证 $d(v)$ 应该尽可能接近 $\frac{2m}{n}$, 我们省略相关细节.

$\square$