拉姆齐定理

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

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

拉姆齊定理不止一條，前述版本的若干引伸仍稱拉姆齊定理。例如，可以將二染色推廣至更多種色，此時定理斷言：對任意色數，和任意正整數，必有某數，使階的完全圖各邊不論如何染色，仍必可找到某（介於至）和某階完全子圖，其各邊皆染第色。可見拉姆齐二染色定理是的特例（同時取）。

例

R (3, 3) = 6 
 
在6個頂點的完全圖內，每邊塗上紅或藍色。欲證必然有一個紅色的三角形或藍色的三角形。

任意選取一個端點，它有5條邊和其他端點相連。
根據鴿巢原理，5條邊染兩種顏色，至少有3邊顏色相同，不失一般性設這種顏色是紅色，又設該三邊為。
三個頂點，互相連結的邊有三條。
若這3條邊中任何一條是紅色，這條邊的兩個端點和便組成一個紅色三角形。
若這3條邊中沒有紅邊，則都是藍色，因此，是藍色三角形。
以上論證對一切染色法都適用，所以的任何二染色皆有同色，換言之。这个定理的通俗版本稱為朋友與陌路人定理。

另一種證法是算兩次：考慮「異色角」的數目，即滿足為紅而為藍的有序三頂點組的個數。若先固定中間的頂點，則對應三元組的數目可能是
（若其全部邊染同色）；
（若有四邊染某色，另一邊不同色）；或
（若有三邊染某色，另兩邊染另一色）。
所以，至多是，而本身有6種可能，異色角的總數至多是。但是，對於三邊不完全同色的三角形，恰好有兩隻異色角，所以，至多有個異色三角形。考慮到6個頂點組成個三角形，至少有兩個是同色三角形，再次得到的結論。

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

1953年普特南數學競賽考過。1947年匈牙利屈爾沙克·約瑟夫數學比賽（）亦然。

R (3, 3, 3) = 17 

多色拉姆齊數就是用三種或更多顏色的拉姆齊數。若不考慮對稱的情況，僅有兩個非平凡的多色拉姆齊數為已知：和。

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

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

的有扭或無扭染色中，選任一顏色，該色邊組成的子圖都是。

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

拉姆齐数

定義
拉姆齐数，用图论的语言有两种描述：
对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；
在着色理论中是这样描述的：对于完全圖的任意一个2边着色，使得中含有一個k阶子完全图，含有一個l阶子完全图，则称满足这个条件的最小的n为一个拉姆齐数。（注意：按照图论的记法表示i阶完全图）

拉姆齐证明，对与给定的正整數数k及l，R(k,l)的答案是唯一和有限的。

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

对于完全圖的每條邊都任意塗上r種顏色之一，分別記為，在中，必定有個顏色為的阶子完全图，或有個顏色為的阶子完全图……或有個顏色為的阶子完全图。符合條件又最少的數n則記為。

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

顯然易見的公式：
R(0,s)=0，
R(1,s)=1，
R(2,s)=s，
（將的順序改變並不改變拉姆齐的數值）。

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

漸近性質 
拉姆齊數滿足不等式。由此，利用數學歸納法，可以證明

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

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

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

雖然上下界皆是指數形式，但兩者底數不同，實際大小相差甚遠，如時，給出的界是。不過，截至2021年，上下界的底數仍毫無改進，依舊是和，僅有較低階項的改進。而且，下界依賴非構造性的概率方法，未有任何確切構造能給出指數下界。暫時所知最佳結果為：

分別為和所證。

至於非對角拉姆齊數，已知其增長級別為；等價說法是，個頂點且的圖，獨立數的最小值用大Θ符號表示成

的上界由、、塞迈雷迪證出，而級的下界原先由（音譯）證明，其後格里菲斯、、菲斯·庞蒂韦罗斯三人和、兩人藉分析「無三角形過程」，分別將下界獨立改進至

一般的非對角拉姆齊數，當固定而增大時，已知最優的上下界為

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

延伸

無窮圖

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

設為無窮集，以表示其兩兩所連邊的集合（即全體二元子集組成的族），每邊染成色之一。則存在同色無窮階完全圖，即有無窮子集，其邊集同色。

證明：取任一。自引出無窮多條邊，必有某色出現無窮多次。記為該些邊另一端點的集合。又取任一，同樣自有無窮多條邊引至，故必有某色及無窮子集，使引至的各邊皆染色。

餘可類推，得到一列互異的元素及一列顏色。由於僅得有限多種色，必有顏色出現無窮多次，即有對於無窮序列成立。此時，有為無窮子集，且其元素兩兩連邊同色（因為邊所染為色），證畢。

本定理對於超圖（即換成）亦成立。

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

無窮推出有限 

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

反設有限拉姆齊定理不成立，即某個拉姆齊數不存在，則有整數和滿足：對任意正整數，完全圖皆有某種染色的方案，而不產生同色的元子集。以表示此種方案的集合。

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

同樣，元素的限制必屬，故可定義為此種限制所得染色法的集合，其不為空。類推對所有正整數定義。

現對每個正整數，有，且逐個集合非空。又為有限集，因為由乘法原理，全體染色方案，不論是否有同色元集，總數是。由此，整個序列的交集非空。又每個的元素來自某元素的限制，可知每個元素都來自元素的限制，從而由的染色出發，可以延拓成的染色，並可重複，直至得到無窮圖的染色，而無同色元集，與無窮拉姆齊定理矛盾。

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

超圖 
定理亦可推廣至超图。一個均勻超圖（或超圖）就是將圖的邊由二元子集換成元子集。超圖拉姆齊定理敍述如下：
對任意正整數和，以及任意正整數，存在拉姆齊數，使得階完全超圖的各邊，不論如何染種色，必存在令圖中可找出某個衹染色的階完全超圖。
此定理一般對歸納證出，的初始情況正如前文。

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

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

已知，，，，，，，。

註

參考文獻

外部链接
证明R(3,6) = 18

拉姆齊理論
L
图染色