拉姆齊二染色定理，在組合數學上，拉姆齊（Ramsey）定理是要解決以下的問題：要找這樣一個最小的數n，使得n個人中必定有k個人相識或l個人互不相識。
基本介紹
- 中文名：拉姆齊二染色定理
- 命名者：弗蘭克·普倫普頓·拉姆齊
- 命名時間：1930年
- 出處：On a Problem in Formal Logic（《形式邏輯上的一個問題》）
來源,相關研究,研究簡介,研究人物,
來源
這個定理以弗蘭克·普倫普頓·拉姆齊命名，1930年他在論文On a Problem in Formal Logic（《形式邏輯上的一個問題》）證明了R(3,3)=6。拉姆齊數的定義拉姆齊數，用圖論的語言有兩種描述：對於所有的N頂圖，包含k個頂的團或l個頂的獨立集。具有這樣性質的最小自然數N就稱為一個拉姆齊數，記作R(k,l)；在著色理論中是這樣描述的：對於完全圖Kn的任意一個2邊著色(e1,e2)，使得Kn[e1]中含有一個k階子完全圖，Kn[e2]含有一個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(1,s)=1， R(2,s)=s， R(l1,l2,l3,...,lr;r)=R(l2,l1,l3,...,lr;r)=R(l3,l1,l2,...,lr;r)（將li的順序改變並不改變拉姆齊的數值）。
r,s | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
3 | 6 | 9 | 14 | 18 | 23 | 28 | 36 | 40-43 |
4 | 9 | 18 | 25 | 35 – 41 | 49 – 61 | 56 – 84 | 73 – 115 | 92-149 |
5 | 14 | 25 | 43 – 49 | 58 – 87 | 80 – 143 | 101 – 216 | 125 – 316 | 143-442 |
6 | 18 | 35 – 41 | 58 – 87 | 102 – 165 | 113 – 298 | 127 – 495 | 169 – 780 | 179-1171 |
7 | 23 | 49 – 61 | 80 – 143 | 113 – 298 | 205 – 540 | 216 – 1031 | 233 – 1713 | 289-2826 |
8 | 28 | 56 – 84 | 101 – 216 | 127 – 495 | 216 – 1031 | 282 – 1870 | 317 – 3583 | 317-6090 |
9 | 36 | 73 – 115 | 125 – 316 | 169 – 780 | 233 – 1713 | 317 – 3583 | 565 – 6588 | 580-12677 |
10 | 40-43 | 92 – 149 | 143 – 442 | 179 – 1171 | 289 – 2826 | 317 – 6090 | 580-12677 | 798-23556 |
R(3,3,3)=17
R(3,3)等於6的證明證明：在一個K6的完全圖內，每邊塗上紅或藍色，必然有一個紅色的三角形或藍色的三角形。任意選取一個端點P，它有5條邊和其他端點相連。根據鴿巢原理，5條邊的顏色至少有3條相同，不失一般性設這種顏色是紅色。在這3條邊除了P以外的3個端點，它們互相連結的邊有3條。若這3條邊中任何一條是紅色，這條邊的兩個端點和P相連的2邊便組成一個紅色三角形。若這3條邊中任何一條都不是紅色，它們必然是藍色，因此，它們組成了一個藍色三角形。而在K5內，不一定有一個紅色的三角形或藍色的三角形。每個端點和毗鄰的兩個端點的線是紅色，和其餘兩個端點的連線是藍色即可。這個定理的通俗版本就是友誼定理。
相關研究
研究簡介
2010年8月，中南大學數學科學與計算技術學院酷愛數理邏輯的劉路在自學反推數學的時候，第一次接觸到拉姆齊二染色定理，並在閱讀大量文獻時發現，海內外不少學者都在進行反推數學中的拉姆齊二染色定理的證明論強度的研究。這是由英國數理邏輯學家西塔潘於上個世紀90年代提出的一個猜想，10多年來許多著名研究者一直努力都沒有解決。同年10月的一天，劉路突然想到利用之前用到的一個方法稍作修改便可以證明這一結論，連夜將這一證明寫出來，投給了數理邏輯國際權威雜誌《符號邏輯雜誌》。
2011年5月，由北京大學、南京大學和浙江師範大學聯合舉辦的邏輯學術會議在浙江師範大學舉行，還是大三學生的劉路應邀參加了這次會議，報告了他對目前反推數學中的拉姆齊二染色定理的證明論強度的研究。劉路的報告給這一懸而未決的公開問題一個否定式的回答，徹底解決了西塔潘的猜想。
劉嘉憶（原名劉路）
劉嘉憶（原名劉路）《符號邏輯雜誌》的主編、邏輯學專家、芝加哥大學數學系鄧尼斯·漢斯傑弗德看到論文後給他寫信：“我是過去眾多研究該問題而無果者之一，看到這一問題的最終解決感到非常高興，特別如你給出的如此漂亮的證明，請接受我對你令人讚嘆的驚奇的成果的祝賀！”同時，鄧尼斯·漢斯傑弗德教授高興地將劉路的研究介紹給了其他幾位同仁和專家，他們一起審讀、反覆商討。
論文審稿人、芝加哥大學博士達米爾·扎法洛夫也認為：“這是一個重要的結果，過去20多年許多著名科研工作者在這方面進行努力。該問題的研究促進了反推數學和計算性理論方面的研究。”
2011年9月16日，美國芝加哥大學數理邏輯學術會議上，雲集了來自歐美的許多數理邏輯專家、學者。大會邀請了12位專家、學者作學術報告，劉路作為亞洲高校唯一一位代表在會上作了40分鐘報告。他在數理邏輯方面的研究成果，讓與會專家、學者對這位來自中國的“80後”投上讚許的目光。劉路表示，他投給《美國數學會彙刊》的論文獲得威士康星大學、伯克利大學等幾位教授很高的評價，有望公開發表。
