圖蘭定理

在圖論中，圖蘭定理（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定理的一個推論。

## 參見

- 艾狄胥－斯通定理 —— 圖蘭定理的推廣，將禁止完全子圖改為禁止一般圖。