拉姆齐定理

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

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

拉姆齊定理不止一條，前述版本的若干引伸仍稱拉姆齊定理。例如，可以將二染色推廣至更多種色，此時定理斷言：對任意色數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)\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。

1953年普特南數學競賽考過R(3, 3) \le 6。1947年匈牙利屈爾沙克·約瑟夫數學比賽（）亦然。

R (3, 3, 3) = 17
Image:K_16 partitioned into three Clebsch graphs.svg|無扭的
Image:K_16 partitioned into three Clebsch graphs twisted.svg|有扭的

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

漸近性質
拉姆齊數滿足不等式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}},

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

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

設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 成立。此時，有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]^{\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階循環賽圖 。

此前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。
注释
参考资料
參考文獻
*.
*
*
*.
*.
*
*.
*.
*.
*
*
*.
*.
*.

外部链接
*[https://web.archive.org/web/20120324144027/http://www.math.sinica.edu.tw/post-doctor/cariolaro/r36.pdf 证明R(3,6) = 18]