拉姆齊定理

在組合數學上，拉姆齊(Ramsey)定理是要解決以下的問題：要找這樣一個最小的數n，使得n個人中必定有k個人相識或l個人互不相識。

6 個人中至少存在3人相互認識或者相互不認識。

該定理等價於證明這6個頂點的完全圖的邊，用紅、藍二色任意着色，必然至少存在一個紅色邊三角形，或藍色邊三角形。

拉姆齊理論的一個典型結果是從一些數學結構開始，然後將其切成碎片。為了確保至少其中一部分具有給定的有趣屬性，原始結構必須達到多大，這個想法可以定義為分區規則。

例如，考慮一個n階的完整圖。也就是説，有n個頂點，並且每個頂點通過一條邊連接到其他每個頂點。 3階的完整圖稱為三角形。然後將每條邊緣都塗成紅色或藍色。為了確保有藍色三角形或紅色三角形，事實證明n必須是6。

表達此結果的另一種方法如下：在至少有六個人的任何一方中，有三個人都是互相認識的（每個人都認識另外兩個）或互相陌生的（每個人都不知道另兩個人）。

這也是拉姆西定理的特例，該定理説，對於任何給定的整數c，任何給定的整數n1，...，nc，都有一個數字R（n1，...，nc），使得如果R（n1，...，nc）階的完整圖的邊用c種不同的顏色着色，那麼對於介於1和c之間的某些i，它必須包含一個ni階的完整子圖，其邊都是i。上面的特殊情況有c = 2和n1 = n2 = 3。

R(3,3)=6

證明如下：首先，把這6個人設為A、B、C、D、E、F六個點。由A點可以引出AB、AC、AD、AE、AF五條線段。設：如果兩個人認識，則設這兩個人組成的線段為紅色；如果兩個人不認識，則設這兩個人組成的線段為藍色。

由抽屜原理可知：這五條線段中至少有三條是同色的。不妨設AB、AC、AD為紅色。若BC或CD為紅色，則結論顯然成立。若BC和CD均為藍色，則若BD為紅色，則一定有三個人相互認識；若BD為藍色，則一定有三個人互相不認識。

對於任何給定的c和n，都有一個數字V，因此，如果V個連續數字用c種不同的顏色着色，則它必須包含長度為n的算術級數，其元素都是相同的顏色。

對於任何給定的n和c，都有一個數字H，如果H維n×n×n×...×n立方體的像元用c色着色，則必須有一行，列等長度為n的所有單元格都具有相同的顏色。那就是：多人n排字遊戲不能以平局結束，無論n有多大，有多少人在玩，如果您在棋盤上有足夠多的人玩尺寸。 Hales-Jewett定理隱含了Van der Waerden定理。

對於任何給定的c，都有一個數字N，如果數字1，2，...，N用c種不同的顏色着色，那麼必須有一對整數x，y，使得x，y和x + y都是相同的顏色。存在該定理的許多概括，包括Rado定理，Rado-Folkman-Sanders定理，Hindman定理和Milliken-Taylor定理。格雷厄姆，羅斯柴爾德和斯賓塞是拉姆齊理論中這些以及其他許多結果的經典參考。

Ramsey理論的結果通常具有兩個主要特徵。首先，它們是非建設性的：它們可能表明存在某種結構，但沒有給出尋找此結構的過程（除了蠻力搜索）。例如，鴿洞原理就是這種形式。其次，儘管拉姆齊理論的結果確實表明足夠大的物體必須一定包含給定的結構，但這些結果的證明通常要求這些物體非常大-呈指數增長或甚至與阿克曼函數一樣快的界線並不罕見。在許多情況下，這些界限是證明的偽像，尚不清楚是否可以對其進行實質性的改進。在其他情況下，已知任何邊界都必須非常大，有時甚至比任何原始遞歸函數還要大；有關示例，請參見Paris-Harrington定理。格雷厄姆數是認真的數學證明中使用的最大數，是與拉姆齊理論有關的問題的上限。

Ramsey理論中的定理通常是三種類型之一。許多定理以Ramsey定理本身為模型，它們斷言在一個大型結構化對象的每個分區中，其中一個類必然包含一個大型結構化子對象，但沒有提供有關這是哪個類的信息。有時，出現此類Ramsey類型結果的原因是最大的分區類始終包含所需的子結構。根據圖蘭定理，這種結果稱為密度結果或圖蘭類型結果。著名的例子包括Szemerédi定理，它是對van der Waerden定理的強化，以及Hales-Jewett定理的密度形式。

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

對於所有的N頂圖，包含k個頂的團或l個頂的獨立集。具有這樣性質的最小自然數N就稱為一個拉姆齊數，記作R(k,l)；

在着色理論中是這樣描述的：對於完全圖Kn的任意一個2邊着色(e1,e2)，使得Kn[e2]中含有一個k邊形，Kn[e1]含有一個l邊形，則稱滿足這個條件的最小的n為一個拉姆齊數。（注意：Ki按照圖論的記法表示i階完全圖）

拉姆齊證明，對與給定的正整數數k及l，R(k,l)的答案是確定和有限的。

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

對於完全圖Kn的每條邊都任意塗上r種顏色之一，分別記為 e1,e2,e3,...,er ，在Kn中，必定有個顏色為e1的l1邊形，或有個顏色為e2的l2邊形……或有個顏色為er的lr邊形。符合條件又最少的數n則記為R(l1,l2,l3,...,lr;r)。

拉姆齊數的數值或上下界

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

已知的拉姆齊數

R(3,3)=6,R(3,4)=R(4,3)=9,R(3,5)=R(5,3)=14,R(3,6)=R(6,3)=18,R(3,7)=R(7,3)=23,R(3,8)=R(8,3)=28

R(3,9)=R(9,3)=36,R(4,4)=18,R(4,5)=R(5,4)=25

拉姆齊數的一些性質：

R(3,3)等於6的證明

證明：在一個K6的完全圖內，每邊塗上紅或藍色，必然有一個紅色的三角形或藍色的三角形。