拉姆齐二染色定理

在組合數學上，**拉姆齊定理**（英語：Ramsey's theorem），又稱**拉姆齊二染色定理**，斷言對任意正整數 $k$ 和 $l$ ，若一個聚會的人數 $n$ 足夠大，則無論相識關係如何，必定有 $k$ 個人相識或 $l$ 個人互不相識。給定 $k,l$ 時，保證前述結論的最小 $n$ 值稱為**拉姆齊數** $R(k,l)$ ，其值取決於 $k,l$ 。用圖論術語複述：若將足夠大的完全圖各邊染紅藍兩色，則不論如何染，必定有紅色的 $k$ 階完全圖或藍色的 $l$ 階完全圖。

拉姆齊定理是組合數學的重要結論，以弗蘭克・普倫普頓・拉姆齊命名。他在 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

在 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)\leq 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)\leq 6$ 的結論。

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

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

### _R_ (3, 3, 3) = 17

* 僅有兩種方法將 16 個頂點之間的邊染三種顏色而無同色三角形
* *

多色拉姆齊數就是用三種或更多顏色的拉姆齊數。若不考慮對稱的情況，僅有兩個非平凡的多色拉姆齊數為已知： $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)\leq 17$ 。

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

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

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

## 拉姆齊數

### 定義

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

1. 對於所有的 N 頂圖，包含 k 個頂的團或 l 個頂的獨立集。具有這樣性質的最小自然數 N 就稱為一個拉姆齊數，記作 R (_k_,_l_)；
2. 在著色理論中是這樣描述的：對於完全圖 $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(r,s)\leq 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\leq R(10,10)\leq 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)}$ 皆有某種染 $c$ 色的方案，而不產生同色的 $T$ 元子集。以 $C_{k}$ 表示此種方案的集合。

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

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

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

以拓撲學觀之，此為標準的緊論證（compactness argument），相當於考慮全體染色的拓撲空間 $[c]^{\binom {\mathbb {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$ 的初始情況正如前文。

### 有向圖

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

此前 $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\leq R(7)\leq 47$ 。

## 註

## 參考文獻

## 外部連結

* 證明 R (3,6) = 18