又稱“拉姆齊二染色定理”，是由英國數理邏輯學家西塔潘於上個世紀90年代提出的壹個猜想。在組合數學上，拉姆齊（Ramsey）定理是要解決以下的問題：要找這樣壹個最小的數n，使得n個人中必定有k個人相識或l個人互不相識。這個定理以弗蘭克·普倫普頓·拉姆齊命名，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 103 6 9 14 18 23 28 36 40 – 434 9 18 25 35 – 41 49 – 61 56 – 84 73 – 115 92 – 1495 14 25 43 – 49 58 – 87 80 – 143 101 – 216 125 – 316 143 – 4426 18 35 – 41 58 – 87 102 – 165 113 – 298 127 – 495 169 – 780 179 – 11717 23 49 – 61 80 – 143 113 – 298 205 – 540 216 – 1031 233 – 1713 289 – 28268 28 56 – 84 101 – 216 127 – 495 216 – 1031 282 – 1870 317 – 3583 317 – 60909 36 73 – 115 125 – 316 169 – 780 233 – 1713 317 – 3583 565 – 6588 580 – 1267710 40 – 43 92 – 149 143 – 442 179 – 1171 289 – 2826 317 – 6090 580 – 12677 798 – 23556R(3,3,3)=17 R(3,3)等於6的證明證明：在壹個K6的完全圖內，每邊塗上紅或藍色，必然有壹個紅色的三角形或藍色的三角形。任意選取壹個端點P，它有5條邊和其他端點相連。根據鴿巢原理，3條邊的顏色至少有兩條相同，不失壹般性設這種顏色是紅色。在這3條邊除了P以外的3個端點，它們互相連結的邊有3條。若這3條邊中任何壹條是紅色，這條邊的兩個端點和P相連的2邊便組成壹個紅色三角形。若這3條邊中任何壹條都不是紅色，它們必然是藍色，因此，它們組成了壹個藍色三角形。而在K5內，不壹定有壹個紅色的三角形或藍色的三角形。每個端點和毗鄰的兩個端點的線是紅色，和其余兩個端點的連線是藍色即可。這個定理的通俗版本就是友誼定理。
上一篇:迷妳世界怎麽找村莊下一篇:攜稅寶每年都要交費嗎