拉姆齐定理

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

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

拉姆齊定理不止一條，前述版本的若干引伸仍稱拉姆齊定理。例如，可以將二染色推廣至更多種色，此時定理斷言：對任意色數$c$，和任意正整數$n_1,n_2,\dots ,n_c$，必有某數$R(n_1,\dots ,n_c)$，使$R(n_1,\dots ,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個頂點組成$(\genfrac{}{}{0ex}{}{6}{3})=20$個三角形，至少有兩個是同色三角形，再次得到$R(3,3)\le 6$的結論。

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

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

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)\le 17$。

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

Template:Le

$K_{16}$的有扭或無扭染色中，選任一顏色，該色邊組成的子圖都是Template:Le。

對較少頂點的完全圖，已知$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)的值，我們要嘗試毀滅這班外星人了。」Template:Cn

顯然易見的公式： 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$的順序改變並不改變拉姆齐的數值）。

拉姆齐数Template:Math的值/已知上下界 Template:OEIS

Template:Diagonal split header	1	2	3	4	5	6	7	8	9	10
1	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes
2		Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes
3			Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Yes	Template:Partial
4				Template:Yes	Template:Yes	Template:Partial	Template:Partial	Template:Partial	Template:Partial	Template:Partial
5					Template:Partial	Template:Partial	Template:Partial	Template:Partial	Template:Partial	Template:Partial
6						Template:Partial	Template:Partial	Template:Partial	Template:Partial	Template:Partial
7							Template:Partial	Template:Partial	Template:Partial	Template:Partial
8								Template:Partial	Template:Partial	Template:Partial
9									Template:Partial	Template:Partial
10										Template:Partial

Template:Le有不定期更新的動態綜述，介紹拉姆齊數的研究成果。

漸近性質

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

$R(r,s)\le (\genfrac{}{}{0ex}{}{r+s-2}{r-1}).$

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

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

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

下界方面，1947年艾狄胥首創Template:Le，證明

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

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

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

分別為Template:Link-en和Template:Link-en所證。

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

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

$R(3,t)$的上界由Template:Link-en、Template:Link-en、塞迈雷迪證出，而$\frac{t^2}{\log t}$級的下界原先由Template:Link-en（音譯）證明，其後格里菲斯、Template:Link-en、菲斯·庞蒂韦罗斯三人和Template:Link-en、Template:Link-en兩人藉分析「無三角形過程」，分別將下界獨立改進至

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

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

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

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

延伸

無窮圖

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

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

證明：取任一$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,\dots \in X$及一列顏色$c_1,c_2,\dots$。由於僅得有限多種色，必有顏色出現無窮多次，即有$c_{i_1}=c_{i_2}=\cdots$對於無窮序列$i_1<i_2<\cdots$成立。此時，有$M=\{x_{i_1},x_{i_2},x_{i_3},\dots \}$為無窮子集，且其元素兩兩連邊同色（因為邊$x_{i_a}{x}_{i_b}$所染為$c_{i_a}$色），證畢。

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

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

無窮推出有限

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

反設有限拉姆齊定理不成立，即某個拉姆齊數不存在，則有整數$c$和$T$滿足：對任意正整數$k$，完全圖$[k{]}^{(2)}$Template:註皆有某種染$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^{(\genfrac{}{}{0ex}{}{k}{2})}$。由此，整個序列的交集$D_k=C_k\cap C_k^1\cap C_k^2\cap \cdots$非空。Template:註又每個$C_k^i$的元素來自$C_{k+1}^{i-1}$某元素的限制，可知$D_k$每個元素都來自$D_{k+1}$元素的限制，從而由$D_k$的染色出發，可以延拓成$D_{k+1}$的染色，並可重複，直至得到無窮圖${\mathbb{N}}^{(2)}$的染色，而無同色$T$元集，與無窮拉姆齊定理矛盾。

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

超圖

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

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

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

有向圖

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

此前$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$。

參考文獻

• Template:Citation.
• Template:Citation
• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation.
• Template:Citation
• Template:Citation
• Template:Citation.
• Template:Citation.
• Template:Citation.

外部链接

• 证明R(3,6) = 18