在組合數學上， 拉姆齊（Ramsey）定理是要解決以下的問題：要找這樣一個最小的數n ，使得n個人中必定有k個人相識或l個人互不相識。
這個定理以弗蘭克·普倫普頓·拉姆齊命名， 1930年他在論文On a Problem in Formal Logic （《形式邏輯上的一個問題》）證明了R(3,3)=6。
基本介紹
- 中文名：拉姆齊定理
- 外文名：Ramsey
- 提出者：弗蘭克·普倫普頓·拉姆齊
- 提出時間：1930
- 套用學科：數學，計算機
- 表達式：R(a,b)個頂點的完全圖
- 適用領域範圍：組合數學
定理定義,通俗表述,驗證推導,拉姆齊數,
定理定義
在組合數學上，拉姆齊(Ramsey)定理是要解決以下的問題：要找這樣一個最小的數n，使得n個人中必定有k個人相識或l個人互不相識。
通俗表述
6 個人中至少存在3人相互認識或者相互不認識。
該定理等價於證明這6個頂點的完全圖的邊，用紅、藍二色任意著色，必然至少存在一個紅色邊三角形，或藍色邊三角形。
驗證推導
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為藍色，則一定有三個人互相不認識。
拉姆齊數
拉姆齊數，用圖論的語言有兩種描述：
對於所有的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
關於拉姆齊數，有
，當a,b大於等於2時。
顯然易見的公式：
1°R(1,s)=1
2°R(2,s)=s R(l1,l2,l3,...,lr;r)=R(l2,l1,l3,...,lr;r)=R(l3,l1,l2,...,lr;r) （將li的順序改變並不改變拉姆齊的數值）
R(3,3)等於6的證明
證明：在一個K6的完全圖內，每邊塗上紅或藍色，必然有一個紅色的三角形或藍色的三角形。
- 任意選取一個端點P ，它有5條邊和其他端點相連。
- 根據鴿巢原理，5條邊的顏色至少有3條相同，不失一般性設這種顏色是紅 色。
- 在這3條邊除了P以外的3個端點，它們互相連結的邊有3條。
- 若這3條邊中任何一條是紅色，這條邊的兩個端點和P相連的2邊便組成一個紅色三角形。
- 若這3條邊中任何一條都不是紅色，它們必然是藍色，因此，它們組成了一個藍色三角形。
- 而在K5內，不一定有一個紅色的三角形或藍色的三角形。 每個端點和毗鄰的兩個端點的線是紅色，和其餘兩個端點的連線是藍色即可。這個定理的通俗版本就是友誼定理 。
