拉姆齊定理

在組合數學上，拉姆齊定理（Ramsey's theorem），又稱拉姆齊二染色定理，斷言對任意正整數$k$和$l$，若一個聚會的人數$n$足夠大，則無論相識關係如何，必定有$k$個人相識或$l$個人互不相識。給定$k, l$時，保證前述結論的最小$n$值稱為拉姆齊數$R(k,l)$，其值取決於$k, l$。用圖論術語複述：若將足夠大的完全圖各邊染紅藍兩色，則不論如何染，必定有紅色的$k$階完全圖或藍色的$l$階完全圖。有些作者如Brualdi及Harary要求$k, l > 1$，以免對單一頂點（從而無邊）的圖的邊染色。亦有Gross和Erdős等作者將兩種色換成有邊與否，從而定理敍述變成：在足夠大的簡單圖中，必有$r$團或$s$獨立集。此形式下或可更自然地考慮單頂點的圖。

拉姆齊定理是組合數學的重要結論，以弗蘭克·普倫普頓·拉姆齊命名。他在1930年論文論形式邏輯的一個問題證明此定理最初的版本，開創現稱拉姆齊理論的組合理論分支。拉姆齊理論的主題是從「無序」尋找「規律」，希望找出某數學結構中，存在規律子結構的一般條件。在拉姆齊定理的圖論表述中，此「規律子結構」是同色集（monochromatic set），即頂點集的子集，其中各邊皆染成同一顏色。

拉姆齊定理不止一條，前述版本的若干引伸仍稱拉姆齊定理。例如，可以將二染色推廣至更多種色，此時定理斷言：對任意色數$c$，和任意正整數$n_1, n_2, \ldots, n_c$，必有某數$R(n_1, \ldots, n_c)$，使$R(n_1, \ldots, n_c)$階的完全圖各邊不論如何染$c$色，仍必可找到某$i$（介於$1$至$c$）和某$n_i$階完全子圖，其各邊皆染第$i$色。可見拉姆齊二染色定理是$c = 2$的特例（同時取$n_1 = k, n_2 = l$）。

## 例

### R (3, 3) = 6

<image>

在6個頂點的完全圖$K_6$內，每邊塗上紅或藍色。欲證必然有一個紅色的三角形或藍色的三角形。

- 任意選取一個端點$P$，它有5條邊和其他端點相連。
- 根據鴿巢原理，5條邊染兩種顏色，至少有3邊顏色相同，不失一般性設這種顏色是紅色，又設該三邊為$PA, PB, PC$。
- $A, B, C$三個頂點，互相連結的邊有$AB, BC, CA$三條。
- 若這3條邊中任何一條是紅色，這條邊的兩個端點和$P$便組成一個紅色三角形。
- 若這3條邊中沒有紅邊，則都是藍色，因此，$ABC$是藍色三角形。

以上論證對一切染色法都適用，所以$K_6$的任何二染色皆有同色$K_3$，換言之$R(3, 3)\le 6$。這個定理的通俗版本稱為朋友與陌路人定理。

另一種證法是算兩次：考慮「異色角」的數目，即滿足$xy$為紅而$yz$為藍的有序三頂點組$(x, y, z)$的個數。若先固定中間的頂點$y$，則對應三元組的數目可能是

- $0 \times 5 = 0$（若其全部邊染同色）。
- $1 \times 4 = 4$（若有四邊染某色，另一邊不同色）；或
- $2\times 3 = 6$（若有三邊染某色，另兩邊染另一色）。

所以，至多是$6$，而$y$本身有6種可能，異色角的總數至多是$6 \times 6 = 36$。但是，對於三邊不完全同色的三角形，恰好有兩隻異色角，所以，至多有$18$個異色三角形。考慮到6個頂點組成$\binom{6}{3} = 20$個三角形，至少有兩個是同色三角形，再次得到$R(3, 3)\le 6$的結論。

反之，將$K_5$二染色，不一定有同色的三角形。此構造在同構意義下唯一，如下圖所示：將五個頂點排成一圈，每個端點和毗鄰的兩個端點之間的連線染紅色，與其餘兩個端點的連線染藍色，則不產生同色三角形。所以，$R(3, 3) = 6$。

<image>

1953年普特南數學競賽考過$R(3, 3) \le 6$。1947年匈牙利屈爾沙克·約瑟夫數學比賽（Kürschák József Matematikai Tanulóverseny）亦然。

### R (3, 3, 3) = 17

<image>

- 無扭的

<image>

- 有扭的

多色拉姆齊數就是用三種或更多顏色的拉姆齊數。若不考慮對稱的情況，僅有兩個非平凡的多色拉姆齊數為已知：$R(3, 3, 3) = 17$和$R(3, 3, 4) = 30$。

設將某完全圖的邊染紅綠藍三色，而無同色三角形。選任一頂點$v$，考慮以紅邊與$v$相連的各點，組成$v$的「紅鄰域」。紅鄰域之內不能再有任何紅邊，否則該紅邊與$v$一同組成紅色三角形。所以紅鄰域內的邊衹用藍綠兩色。由上節$R(3, 3) = 6$，$v$的紅鄰域最多衹有5個頂點，否則有藍或綠的同色三角形。同理，$v$的綠鄰域和藍鄰域，各有至多5個頂點，但圖中每個頂點，或為$v$本身，或屬$v$的某色鄰域，所以全圖至多$1+5+5+5 = 16$個頂點。故$R(3, 3, 3) \le 17$。

欲證$R( 3, 3, 3) = 17$，現需用三種顏色畫出16個頂點的完全圖，而不產生同色三角形。若不辨同構之異，則恰有兩種畫法，分別稱為「無扭」（untwisted）和「有扭」（twisted）染法，見上圖。

<image>

$K_{16}$的有扭或無扭染色中，選任一顏色，該色邊組成的子圖都是克萊布希圖。

對較少頂點的完全圖，已知$K_{15}$亦衹得兩種染三色的方法無同色三角形，分別來自$K_{16}$的兩種染法，刪去任意一個頂點。$K_{14}$則有115種方法染三色而無同色三角形，但此數不僅不辨圖同構（頂點的置換），還不辨顏色的置換。

## 拉姆齊數

### 定義

拉姆齊數，用圖論的語言有兩種描述：

- 對於所有的N頂圖，包含k個頂的團或l個頂的獨立集。具有這樣性質的最小自然數N就稱為一個拉姆齊數，記作R(k,l)。
- 在著色理論中是這樣描述的：對於完全圖$K_n$的任意一個2邊著色$(e_1,e_2)$，使得$K_n[e_1]$中含有一個k階子完全圖，$K_n[e_2]$含有一個l階子完全圖，則稱滿足這個條件的最小的n為一個拉姆齊數。（注意：$K_i$按照圖論的記法表示i階完全圖）

拉姆齊證明，對與給定的正整數數k及l，R(k,l)的答案是唯一和有限的。

拉姆齊數亦可推廣到多於兩個數：

對於完全圖$K_n$的每條邊都任意塗上r種顏色之一，分別記為$e_1,e_2,e_3, ... , e_r$，在$K_n$中，必定有個顏色為$e_1$的$l_1$階子完全圖，或有個顏色為$e_2$的$l_2$階子完全圖……或有個顏色為$e_r$的$l_r$階子完全圖。符合條件又最少的數n則記為$R(l_1,l_2,l_3, ... , l_r)$。

### 數值或上下界

已知的拉姆齊數非常少，保羅·艾狄胥曾以一個譬喻來描述尋找拉姆齊數的難度：「想像有隊外星人軍隊在地球降落，要求取得R(5,5)的值，否則便會毀滅地球。在這個情況，我們應該集中所有電腦和數學家嘗試去找這個數值。若他們要求的是R(6,6)的值，我們要嘗試毀滅這班外星人了。」

顯然易見的公式：

R(0,s)=0。

R(1,s)=1。

R(2,s)=s。

$\mathrm{R}(l_1,l_2,l_3, ... , l_r) =R(l_2,l_1,l_3, ... , l_r) =R(l_3,l_1,l_2, ... , l_r)$（將$l_i$的順序改變並不改變拉姆齊的數值）。

r｜1｜2｜3｜4｜5｜6｜7｜8｜9｜10

1｜1｜1｜1｜1｜1｜1｜1｜1｜1｜1

2｜2｜3｜4｜5｜6｜7｜8｜9｜10

3｜6｜9｜14｜18｜23｜28｜36｜40–41

$R(3,10) \leq 41$

4｜18｜25｜36–41｜49–61｜59–84｜73–115｜92–149

5｜43–46｜58–87｜80–143｜101–216｜133–316｜149–442

6｜102–165｜115–298｜134–495｜183–780｜204–1171

7｜205–540｜217–1031｜252–1713｜292–2826

8｜282–1870｜329–3583｜343–6090

9｜565–6588｜581–12677

10｜798–23556

組合電子期刊有不定期更新的動態綜述，介紹拉姆齊數的研究成果。

### 漸近性質

拉姆齊數滿足不等式$R(r, s) \le R(r - 1, s) + R(r, s - 1)$。由此，利用數學歸納法，可以證明

$$R(r, s) \leq \binom{r + s - 2}{r - 1}.$$

上述結果歸功於艾狄胥和塞凱賴什。當$r = s$時，用史特靈公式化成：

$$R(s, s) \leq [1 + o(1)]\frac{4^{s - 1}}{\sqrt{\pi s}},$$

其中誤差項o (1)，當$s$趨向於無窮時，趨向$0$。

下界方面，1947年艾狄胥首創機率法，證明

$$R(s, s) \geq [1 + o(1)] \frac{s}{\sqrt{2} e} 2^{s/2}.$$

雖然上下界皆是指數形式，但兩者底數不同，實際大小相差甚遠，如$s = 10$時，給出的界是$101 \le R(10, 10) \le 48620$。不過，截至2021年，上下界的底數仍毫無改進，依舊是$4$和$\sqrt 2$，僅有較低階項的改進。而且，下界依賴非構造性的機率方法，未有任何確切構造意即多項式時間演算法的輸出結果。能給出指數下界。暫時所知最佳結果為：

$$[1 + o(1)] \frac{\sqrt{2} s}{e} 2^{\frac{s}{2}} \leq R(s, s) \leq s^{-(c \log s)/(\log \log s)} 4^s,$$

分別為喬爾·斯賓塞和大衛·康倫所證。

至於非對角拉姆齊數$R(3, t)$，已知其增長級別為$\tfrac{t^2}{\log t}$；等價說法是，$n$個頂點且無三角形圖的圖$G$，獨立數$\alpha(G)$的最小值用大Θ符號表示成

$$\Theta \left (\sqrt{n\log n} \right ).$$

$R(3, t)$的上界由奧伊陶伊·米克洛什、科姆洛什·亞諾什、塞邁雷迪證出，而$\tfrac{t^2}{\log t}$級的下界原先由金正翰（音譯）證明，其後格里菲斯、羅伯特·莫里斯 (數學家)、菲斯·龐蒂韋羅斯三人和湯姆·波曼、彼得·基瓦什兩人藉分析「無三角形過程」，分別將下界獨立改進至

$$\left(\frac{1}{4} - o(1)\right)\frac{k^2}{\log k}.$$

一般的非對角拉姆齊數$R(s, t)$，當$s$固定而$t$增大時，已知最優的上下界為

$$c'_s \frac{t^{\frac{s + 1}{2}}}{(\log t)^{\frac{s + 1}{2} - \frac{1}{s - 2}}} \leq R(s, t) \leq c_s \frac{t^{s - 1}}{(\log t)^{s - 2}},$$

分別歸功於波曼、基瓦什兩人和奧伊陶伊、科姆洛什、塞邁雷迪三人。

## 延伸

### 無窮圖

本定理可引伸適用於無窮圖，同樣稱為拉姆齊定理。與有限圖的拉姆齊定理相提並論時，或稱無窮拉姆齊定理（Infinite Ramsey theorem）以作區分。

設$X$為無窮集，以$X^{(2)}$表示其兩兩所連邊的集合（即$X$全體二元子集組成的族），每邊染成$c$色之一。則存在同色無窮階完全圖，即有無窮子集$M\subseteq X$，其邊集$M^{(2)}$同色。

證明：取任一$x_1 \in X$。自$x_1$引出無窮多條邊，必有某色$c_1$出現無窮多次。記$X_1 \subseteq X \setminus \{x_1\}$為該些邊另一端點的集合。又取任一$x_2\in X_1$，同樣自$x_2$有無窮多條邊引至$X_1 \setminus \{x_2\}$，故必有某色$c_2$及無窮子集$X_2 \subseteq X_1 \setminus \{x_2\}$，使$x_2$引至$X_2$的各邊皆染$c_2$色。

餘可類推，得到一列互異的元素$x_1, x_2, \ldots \in X$及一列顏色$c_1, c_2, \ldots$。由於僅得有限多種色，必有顏色出現無窮多次，即有$c_{i_1} = c_{i_2} = \cdots$對於無窮序列$i_1 < i_2 < \cdots$成立。此時，有$M = \{ x_{i_1}, x_{i_2}, x_{i_3}, \ldots \}$為無窮子集，且其元素兩兩連邊同色（因為邊$x_{i_a}x_{i_b}$所染為$c_{i_a}$色），證畢。

本定理對於超圖（即$X^{(2)}$換成$X^{(r)}$）亦成立。

關於無窮圖的二染色，艾狄胥－杜什尼克－米勒定理是較強的結果，但其中兩種顏色不對等。定理斷言，任意無窮圖（頂點數不必可數）的邊若染紅藍兩色，則或有可數無窮大的紅色完全子圖，或有與原圖同樣大的藍色完全子圖。

#### 無窮推出有限

運用反證法，可以證明無窮拉姆齊定理推出有限拉姆齊定理。

反設有限拉姆齊定理不成立，即某個拉姆齊數不存在，則有整數$c$和$T$滿足：對任意正整數$k$，完全圖$[k]^{(2)}$為方便起見，頂點集設為$[k] = \{1, 2, 3, \ldots, k\}$。皆有某種染$c$色的方案，而不產生同色的$T$元子集。以$C_k$表示此種方案的集合。

對任意$k$，可將$C_{k+1}$中任意一種染色限制到子圖$[k]^{(2)}$（即刪去頂點$k+1$），不會額外產生同色的$T$元子集，所以所得的染色仍在$C_k$中。$C_k$中，某些染色是以上述方式，由$C_{k+1}$的染色限制而成，此種染色構成$C_k$的子集，記為$C^1_k$。由假設，$C_{k+1}$非空，所以$C^1_k$亦非空。

同樣，$C^1_{k+1}$元素的限制必屬$C^1_k$，故可定義$C^2_k$為此種限制所得染色法的集合，其不為空。類推對所有正整數$m, k$定義$C^m_k$。

現對每個正整數$k$，有$C_k\supseteq C^1_k\supseteq C^2_k\supseteq \cdots$，且逐個集合非空。又$C_k$為有限集，因為由乘法原理，全體染色方案，不論是否有同色$T$元集，總數是$c^{\binom{k}{2}}$。由此，整個序列的交集$D_k=C_k\cap C^1_k\cap C^2_k\cap \cdots$非空。考慮元素個數的最小值為何。又每個$C_k^i$的元素來自$C_{k+1}^{i-1}$某元素的限制，可知$D_k$每個元素都來自$D_{k+1}$元素的限制，從而由$D_k$的染色出發，可以延拓成$D_{k+1}$的染色，並可重複，直至得到無窮圖$\N^{(2)}$的染色，而無同色$T$元集，與無窮拉姆齊定理矛盾。

以拓撲學觀之，此為標準的緊論證（compactness argument），相當於考慮全體染色的拓撲空間$[c]^{\binom{\N}{2}}$，而由吉洪諾夫定理，其為若干個有限（從而緊）空間$[c]$之積，所以仍為緊。而條件「在子圖$[k]^{(2)}$上不產生同色$T$元集」，描述該空間的一個閉開集，所以有限交非空推出全體交非空。

### 超圖

定理亦可推廣至超圖。一個$m$均勻超圖（或$m$超圖）就是將圖的邊由二元子集換成$m$元子集。超圖拉姆齊定理敍述如下：

對任意正整數$m$和$c$，以及任意正整數$n_1, n_2, \ldots, n_c$，存在拉姆齊數$R(n_1, \ldots, n_c; c, m)$，使得$R(n_1, \ldots, n_c; c, m)$階完全$m$超圖的各邊，不論如何染$c$種色，必存在$i$令圖中可找出某個衹染$i$色的$n_i$階完全$m$超圖。

此定理一般對$m$歸納證出，$m = 2$的初始情況正如前文。

### 有向圖

亦可定義有向圖的拉姆齊數，最早由提出。設$R(n)$為最小的正整數$Q$，使得$Q$階完全圖中，若為每邊賦兩種定向之一（所得有向圖稱為循環賽圖），則必有無圈的$n$階循環賽圖又稱遞移（transitive）循環賽圖。

此前$R(n, n; 2)$定義為保證$Z$階完全無向圖染兩色會有同色完全$n$階子圖的最小$Z$值，可見$R(n)$是$R(n, n; 2)$的有向類比：兩種顏色現換成邊的兩種方向，而「同色」換成「全部邊方向統一」（所以無圈）。

已知$R(0) = 0$，$R(1) = 1$，$R(2) = 2$，$R(3) = 4$，$R(4) = 8$，$R(5) = 14$，$R(6) = 28$，$34 \le R(7) \le 47$。