图兰定理

在图论中，图兰定理（Turán's theorem）给出了不包含特定大小完全子图（克里克，Clique）的无向图中，边数的最大上界。它是极值图论（Extremal graph theory）的核心结果之一。极值图论主要研究满足给定性质的最大或最小图，而图兰定理则是禁子图问题（Forbidden subgraph problem）中禁止特定完全子图的一个特例。

一个不包含 $(r+1)$ 个顶点的完全图 $K_{r+1}$ 的 $n$ 顶点图的例子可以这样构造：将 $n$ 个顶点分成 $r$ 个大小相等或尽可能相等的集合，若两个顶点属于不同的集合，则在它们之间连一条边。这样得到的图称为图兰图（Turán graph）$T(n,r)$。图兰定理指出，在所有不含 $K_{r+1}$（即 $K_{r+1}$-free）的 $n$ 顶点图中，图兰图拥有的边数最多。

图兰定理及其极端情况的图兰图，最早由匈牙利数学家图兰·帕尔（Pál Turán）于 1941 年提出并研究。在无三角形图（Triangle-free graph，即 $r=2$）的特殊情况下，该定理称为曼特尔定理（Mantel's theorem），由荷兰数学家威廉·曼特尔（Willem Mantel）于 1907 年提出。

## 叙述

图兰定理指出，任何不包含 $K_{r+1}$ 作为子图的 $n$ 顶点图 $G$，其边数最多不超过图兰图 $T(n,r)$ 的边数。对于固定的 $r$ 值，该图的边数为：

$$\left(1-\frac{1}{r}+o(1)\right) \frac{n^2}{2}$$

直观上，这意味着随着 $n$ 的增大，包含在 $T(n,r)$ 中的边所占的比例越来越接近 $1-\frac{1}{r}$。以下许多证明仅给出上界 $\left(1-\frac{1}{r}\right)\frac{n^2}{2}$。

## 证明

马丁·艾格纳（Martin Aigner）与甘特·齐格勒（Günter M. Ziegler）在 2018 年的著作中列举了图兰定理的五种不同证明。其中许多证明都将问题归结为图是完全多部图（Complete multipartite graph）的情况，并证明当 $r$ 个部分的尺寸尽可能接近相等时，边数达到最大。

### 数学归纳法

<image>

这是图兰最初的证明。考虑一个不含 $K_{r+1}$ 的 $n$ 顶点图，且其边数达到最大。在图中找到一个完全子图 $K_r$（由于边数极大性，此子图必然存在），并将顶点集划分为包含该 $K_r$ 的 $r$ 个顶点的集合 $A$，以及其余 $n-r$ 个顶点的集合 $B$。

现在，我们可以对边数进行上界估计：

- 集合 $A$ 内部的边数恰好为 $\binom{r}{2}$。
- 集合 $A$ 与 $B$ 之间的边数最多为 $(r-1)|B|=(r-1)(n-r)$，因为 $B$ 中的任何顶点都不能与 $A$ 中的所有顶点相连（否则会形成 $K_{r+1}$）。
- 根据归纳假设，集合 $B$ 内部的边数最多为图兰图 $T(n-r,r)$ 的边数。

将这些上界相加，即可得到结果。

### 最大度数顶点法

<image>

这个证明由艾狄胥·帕尔（Paul Erdős）提出。设顶点 $v$ 是图中度数最大的顶点。考虑与 $v$ 不相邻的顶点集合 $A$，以及与 $v$ 相邻的顶点集合 $B$。

现在，删除 $A$ 内部的所有边，并在 $A$ 中的每个顶点与 $B$ 中的每个顶点之间连边。根据最大度数的假设，这样操作会使图的总边数不减，且图依然保持不含 $K_{r+1}$ 的性质。此时，集合 $B$ 内部不包含 $K_r$，因此可以对 $B$ 重复上述步骤。

不断重复此操作，最终会产生一个与图兰图形式相同的图，即一组独立集的集合，且任意两个属于不同独立集的顶点之间都有边相连。简单的计算表明，当所有独立集的大小尽可能接近相等时，该图的边数达到最大。

### 完全多部图优化

这个证明与齐科夫对称化（Zykov Symmetrization）证明类似，都涉及将问题简化为图是完全多部图的情况，并证明当存在 $r$ 个独立集且它们的大小尽可能接近相等时，边数达到极大。步骤如下：

设 $S_1, S_2, \ldots, S_r$ 为该多部图的独立集。由于两个顶点之间有边相连当且仅当它们不在同一个独立集中，因此边数为：

$$\sum_{i \neq j} \left|S_i\right|\left|S_j\right|=\frac{1}{2}\left(n^2-\sum_{i} \left|S_i\right|^2\right),$$

其中左式来自直接计数，右式来自补集计数。为了证明 $\left(1-\frac{1}{r}\right)\frac{n^2}{2}$ 的上界，只需对右式的 $\sum\limits_i\left|S_i\right|^2$ 项应用柯西-施瓦茨不等式（Cauchy–Schwarz inequality），并利用 $\sum\limits_i\left|S_i\right|=n$ 即可。

为了进一步证明图兰图是最优的，可以证明没有任何两个 $S_i$ 的大小相差超过 1。具体来说，假设对于某些 $i \neq j$，有 $\left|S_i\right| \geq \left|S_j\right|+2$，那么将一个顶点从 $S_i$ 移动到 $S_j$（并相应地调整边）将会增加上述边数总和的值。这可以透过检查上述边数表达式两侧的变化来观察，或者注意到被移动顶点的度数增加了。

### 拉格朗日乘子法

这个证明由莫茨金（Theodore Motzkin）与斯特劳斯（Ernst G. Straus）于 1965 年提出。他们首先考虑一个不含 $K_{r+1}$ 的图，其顶点标号为 $1,2,\ldots,n$，并考虑在所有非负且和为 1 的 $x_1,x_2,\ldots,x_n$ 上最大化以下函数：

$$f(x_1,x_2,\ldots,x_n)=\sum_{i,j\ \text{adjacent}} x_ix_j$$

该函数被称为该图及其边的拉格朗日函数（Lagrangian）。

证明的核心思想是：如果 $x_i, x_j$ 均不为零，且在图中顶点 $i, j$ 不相邻，则函数：

$$f(x_1,\ldots,x_i-t,\ldots,x_j+t,\ldots,x_n)$$

关于 $t$ 是线性的。因此，可以在不减少函数值的情况下，将 $(x_i,x_j)$ 替换为 $(x_i+x_j,0)$ 或 $(0,x_i+x_j)$。依此类推，必然存在一个最大值点，其中最多只有 $r$ 个变数不为零。

此时，利用柯西-施瓦茨不等式可知，最大值最多为 $\frac{1}{2}\left(1-\frac{1}{r}\right)$。若将所有的 $x_i$ 都代入 $\frac{1}{n}$，可得最大值至少为 $\frac{|E|}{n^2}$，从而得出所需的边数上界。

### 几率方法

此证明中的核心断言由 Caro 和 Wei 独立发现。本证明由诺加·阿隆（Noga Alon）和乔尔·斯宾塞（Joel Spencer）收录于其著作《几率方法》（The Probabilistic Method）中。证明表明，任何顶点度数为 $d_1,d_2,\ldots,d_n$ 的图，都包含一个大小至少为以下值的独立集：

$$S=\frac{1}{d_1+1}+\frac{1}{d_2+1}+\cdots+\frac{1}{d_n+1}.$$

寻找该独立集的随机过程如下：

- 考虑不含 $K_{r+1}$ 的图的顶点的一个随机排列。
- 选择所有满足“与其在排列中排在它之前的任何顶点都不相邻”的顶点。

一个度数为 $d$ 的顶点被选中的几率为 $\frac{1}{d+1}$，因此该过程选出的顶点数平均值为 $S$。

将此结论应用于原图的补图（Complement graph），并使用柯西-施瓦茨不等式对选定集合的大小进行下界估计，即可证明图兰定理。详见条件几率方法中有关图兰定理的应用。

### 齐科夫对称化

<image>

<image>

Aigner 和 Ziegler 将他们收录的五种证明中的最后一种称为“其中最美的一个”。该方法的起源尚不完全清楚，但通常被称为齐科夫对称化（Zykov Symmetrization），因为它曾被用于齐科夫对图兰定理推广的证明中。该证明通过对一个不含 $K_{r+1}$ 的图执行特定步骤，使其在增加边数的同时更接近图兰图。

具体而言，给定一个不含 $K_{r+1}$ 的图，执行以下步骤：

- 如果 $u, v$ 是不相邻的顶点，且 $u$ 的度数高于 $v$，则将 $v$ 替换为 $u$ 的一个复制（即令 $v$ 与所有 $u$ 的邻居相连，并删除 $v$ 原本的边）。重复此操作，直到所有不相邻的顶点都具有相同的度数。
- 如果存在顶点 $u, v, w$，满足 $u, v$ 不相邻且 $v, w$ 不相邻，但 $u, w$ 相邻，则将 $u$ 和 $w$ 都替换为 $v$ 的复制。

所有这些步骤都能在保持图不含 $K_{r+1}$ 的同时增加边的数量。

最终，不相邻关系在图中形成了一个等价关系。等价类表明，任何极大图都具有与图兰图相同的形式。如同最大度数顶点证明一样，简单的计算表明，当所有独立集的大小尽可能接近相等时，边数达到最大。

## 曼特尔定理

图兰定理在 $r=2$ 时的特例即为曼特尔定理（Mantel's theorem）：一个不含三角形（Triangle-free）的 $n$ 顶点图中，边数的最大值为 $\lfloor n^2/4 \rfloor.$ 换句话说，人们必须删除 $K_n$ 中略多于一半的边才能获得一个不含三角形的图。

曼特尔定理的一个加强版本指出，任何边数至少为 $n^2/4$ 的哈密顿图，要么是完全二分图 $K_{n/2,n/2}$，要么是全圈图（Pancyclic graph）：它不仅包含三角形，还必须包含长度从 3 直到图中顶点数的所有可能长度的圈。

另一个加强版本指出，每个 $n$ 顶点图的边最多可以被 $\lfloor n^2/4 \rfloor$ 个完全子图（这些子图只能是单条边或三角形）所覆盖。因此，图的交集数（Intersection number，覆盖所有边所需的最少团数）最多为 $\lfloor n^2/4 \rfloor$。

## 超图与图兰密度

对于 $k$-均匀超图（$k$-uniform hypergraphs），目前还没有类似图兰定理的精确结论。事实上，在图兰最初的论文中，他询问了一个具有 $n$ 个顶点的 $3$-均匀超图，在不包含 4 个顶点的完全 3-均匀超图 $K_4^{(3)}$ 的情况下，最多可以有多少条超边。这个超边的最大数量被称为“极值数”（Extremal number）。

更一般地，对于一个超图 $F$，在 $n$ 个顶点上不包含 $F$ 副本的 $k$-均匀超图的最大超边数记为 ex$(n,F)$。为了获得一个更简洁的参数，将 $F$ 的图兰密度（Turán density）$\pi(F)$ 定义为以下极限：

$$\pi(F) = \lim_{n\to \infty}\frac{\text{ex}(n,F)}{\binom{n}{k}}.$$

不难看出序列 $\text{ex}(n,F)/\tbinom{n}{k}$ 是非递增的，因此上述极限总是收敛的。

在该表述下，图兰关于 $K_4^{(3)}$ 的问题（近似解）等价于确定图兰密度 $\pi(K_4^{(3)})$。我们也可以验证 $\pi(K_t^{(k)})=1-\Theta_k(t^{k-1})$。该密度的上界可以通过几率方法或超饱和性（Supersaturation）获得，而下界则可以通过 $\lfloor(t-1)/(k-1)\rfloor$ 个完全子图的不交并的补集来构造。

## 推广

### 其他禁子图

图兰定理表明，在不含 $K_{r+1}$ 的图中，最大的边数为 $\left(1-\frac{1}{r}+o(1)\right) \frac{n^2}{2}$。而艾狄胥－斯通定理（Erdős–Stone theorem）则在 $o(n^2)$ 的误差范围内，给出了禁止任何其他子图 $H$ 时的边数：

（艾狄胥－斯通定理）设 $H$ 是一个色数为 $\chi(H)$ 的图。在不包含 $H$ 作为子图的图中，可能拥有的最大边数为：

$$\left(1-\frac{1}{\chi(H)-1}+o(1)\right) \frac{n^2}{2}$$

其中 $o(1)$ 常数仅取决于 $H$。

传统上，图兰图 $T(n,\chi(H)-1)$ 不能包含 any $H$ 的副本，因此图兰图确立了该下界。由于 $K_{r+1}$ 的色数为 $r+1$，图兰定理正是 $H$ 为 $K_{r+1}$ 时的特殊情况。

在图中不含特定子图 $H$ 的情况下最多能包含多少条边的一般性问题，被称为禁子图问题。

### 最大化其他数量

图兰定理的另一个自然推广是：如果一个图不包含 $K_{r+1}$，它最多可以包含多少个 $K_a$ 副本？图兰定理是 $a=2$ 的情况。齐科夫定理（Zykov's Theorem）回答了这个问题：

（齐科夫定理）在所有不含 $K_{r+1}$ 的 $n$ 顶点图中，包含最多 $K_a$ 副本的图是图兰图 $T(n,r)$。

这最早由齐科夫 (1949) 利用齐科夫对称化证明。由于图兰图包含 $r$ 个大小约为 $\frac{n}{r}$ 的部分，因此 $T(n,r)$ 中 $K_a$ 的数量约为 $\binom{r}{a}\left(\frac{n}{r}\right)^a$。

Alon 和 Shikhelman 于 2016 年发表的一篇论文给出了以下推广，这与图兰定理的 Erdős-Stone 推广类似：

（Alon-Shikhelman, 2016）设 $H$ 是一个色数为 $\chi(H)>a$ 的图。在不含 $H$ 副本的图中，$K_a$ 的最大可能数量为：

$$(1+o(1))\binom{\chi(H)-1}{a}\left(\frac{n}{\chi(H)-1}\right)^a.$$

与 Erdős–Stone 定理类似，图兰图 $T(n,\chi(H)-1)$ 达到了所需的 $K_a$ 副本数量。

### 边-完全子图区域

图兰定理指出，如果一个图的边同态密度（Homomorphism density）严格大于 $1-\frac{1}{r-1}$，则它包含非零个 $K_r$。一个更一般性的问题是：如果给定一个图的边密度，我们可以对其 $K_r$ 的密度说些什么？

回答这个问题的一个难点在于，对于给定的边密度，某个界限可能无法由任何有限图精确达到，但可以由某个无限图序列逼近。为了处理这个问题，人们通常会考虑加权图或图极限（Graphons）。图极限包含了任何图序列的极限值。

对于给定的边密度 $d$，能使 $K_r$ 密度最大化的构造如下：

取顶点数 $N$ 趋于无穷大。挑选其中 $\sqrt{d}N$ 个顶点组成的集合，当且仅当两个顶点都在该选定集合中时，在它们之间连边。

这给出了 $d^{r/2}$ 的 $K_r$ 密度。而使 $K_r$ 密度最小化的构造如下：

取顶点数趋于无穷大。设 $t$ 为满足 $1-\frac{1}{t-1} < d \leq 1-\frac{1}{t}$ 的整数。考虑一个 $t$-部图，其中除了唯一一个最小的部分外，其余所有部分的大小都相等，并且各部分的大小经过精心选择，使得总边密度恰好为 $d$。

对于 $d\leq 1-\frac{1}{r-1}$，这给出了一个 $(r-1)$-部图，因此不包含任何 $K_r$。

三角形情况的下界由 Razborov (2008) 证明，随后由 Reiher (2016) 推广到所有完全子图。上界则是Kruskal–Katona定理的一个推论。

## 参见

- 艾狄胥－斯通定理 —— 图兰定理的推广，将禁止完全子图改为禁止一般图。