拉姆齐定理

在組合數學上，拉姆齐定理（英語：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)的值/已知上下界 （OEIS數列A212954）

s 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–42
4				18	25	36–41	49–61	59–84	73–115	92–149
5					43–48	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)\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$。

參考文獻

• Ajtai, Miklós; Komlós, János; Szemerédi, Endre, A note on Ramsey numbers, J. Combin. Theory Ser. A, 1980, 29 (3): 354–360, doi:10.1016/0097-3165(80)90030-8  .
• Bohman, Tom; Keevash, Peter, The early evolution of the H-free process, Invent. Math., 2010, 181 (2): 291–336, Bibcode:2010InMat.181..291B, S2CID 2429894, arXiv:0908.0429 , doi:10.1007/s00222-010-0247-x 
• Brualdi, Richard A., Introductory Combinatorics 5th, Prentice-Hall: 77–82, 2010, ISBN 978-0-13-602040-0 
• Conlon, David, A new upper bound for diagonal Ramsey numbers, Annals of Mathematics, 2009, 170 (2): 941–960, MR 2552114, S2CID 9238219, arXiv:math/0607788v1 , doi:10.4007/annals.2009.170.941 .
• Erdős, Paul, Some remarks on the theory of graphs, Bull. Amer. Math. Soc., 1947, 53 (4): 292–294, doi:10.1090/S0002-9904-1947-08785-1  .
• Erdős, P.; Moser, L., On the representation of directed graphs as unions of orderings (PDF), A Magyar Tudományos Akadémia, Matematikai Kutató Intézetének Közleményei, 1964, 9: 125–132 [2023-11-06], MR 0168494, （原始内容存档 (PDF)于2022-12-23） 
• Erdős, Paul; Szekeres, George, A combinatorial problem in geometry (PDF), Compositio Mathematica, 1935, 2: 463–470 [2023-11-06], ISBN 978-0-8176-4841-1, doi:10.1007/978-0-8176-4842-8_3, （原始内容存档 (PDF)于2023-11-06） .
• Exoo, G., A lower bound for R(5,5), Journal of Graph Theory, 1989, 13: 97–98, doi:10.1002/jgt.3190130113 .
• Graham, R.; Rothschild, B.; Spencer, J. H., Ramsey Theory, New York: John Wiley and Sons, 1990 .
• Gross, Jonathan L., Combinatorial Methods with Computer Applications, CRC Press: 458, 2008, ISBN 978-1-58488-743-0 
• Harary, Frank, Graph Theory, Addison-Wesley: 16–17, 1972, ISBN 0-201-02787-9 
• Ramsey, F. P., On a problem of formal logic, Proceedings of the London Mathematical Society, 1930, 30: 264–286, doi:10.1112/plms/s2-30.1.264 .
• Spencer, J., Ramsey's theorem – a new lower bound, J. Combin. Theory Ser. A, 1975, 18: 108–115, doi:10.1016/0097-3165(75)90071-0  .
• Bian, Zhengbing; Chudak, Fabian; Macready, William G.; Clark, Lane; Gaitan, Frank, Experimental determination of Ramsey numbers, Physical Review Letters, 2013, 111 (13): 130505, Bibcode:2013PhRvL.111m0505B, PMID 24116761, S2CID 1303361, arXiv:1201.1842 , doi:10.1103/PhysRevLett.111.130505 .

外部链接

• 证明R(3,6) = 18