拉姆齊二染色定理

拉姆齊二染色定理

拉姆齊二染色定理,這個定理以弗蘭克·普倫普頓·拉姆齊命名,在組合數學上,拉姆齊(Ramsey)定理是要解決以下的問題:要找這樣一個最小的數n,使得n個人中必定有k個人相識或l個人互不相識。

來源

拉姆齊二染色定理以弗蘭克·普倫普頓·拉姆齊命名,1930年他在論文OnaProbleminFormalLogic(《形式邏輯上的一個問題》)證明了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,s345678910
369141823283640 – 43
49182535 – 4149 – 6156 – 8473 – 11592 – 149
5142543 – 4958 – 8780 – 143101 – 216125 – 316143 – 442
61835 – 4158 – 87102 – 165113 – 298127 – 495169 – 780179 – 1171
72349 – 6180 – 143113 – 298205 – 540216 – 1031233 – 1713289 – 2826
82856 – 84101 – 216127 – 495216 – 1031282 – 1870317 – 3583317 – 6090
93673 – 115125 – 316169 – 780233 – 1713317 – 3583565 – 6588580 – 12677
1040 – 4392 – 149143 – 442179 – 1171289 – 2826317 – 6090580 – 12677798 – 23556

證明

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

證明:在一個K6的完全圖內,每邊塗上紅或藍色,必然有一個紅色的三角形或藍色的三角形。任意選取一個端點P,它有5條邊和其他端點相連。根據鴿巢原理,3條邊的顏色至少有兩條相同,不失一般性設這種顏色是紅色。在這3條邊除了P以外的3個端點,它們互相連結的邊有3條。若這3條邊中任何一條是紅色,這條邊的兩個端點和P相連的2邊便組成一個紅色三角形。若這3條邊中任何一條都不是紅色,它們必然是藍色,因此,它們組成了一個藍色三角形。而在K5內,不一定有一個紅色的三角形或藍色的三角形。每個端點和毗鄰的兩個端點的線是紅色,和其餘兩個端點的連線是藍色即可。這個定理的通俗版本就是友誼定理。

破解

拉姆齊二染色定理被大三學生破解拉姆齊二染色定理被大三學生劉嘉憶破解

2011年5月,由北京大學等聯合舉辦的邏輯學術會議上,還是大三的劉嘉憶報告了他對反推數學中的拉姆齊(Ramsly)二染色定理的證明論強度的研究。這是由英國數理邏輯學家Seetapun於20個世紀90年代提出的一個猜想,十多年來,許多著名研究者一直努力都沒有解決。
劉嘉憶的報告給這一懸而未決的公開問題一個否定式的回答,徹底解決了Seetapun的猜想。

相關詞條

相關搜尋

熱門詞條

聯絡我們