<address id="drfjd"><form id="drfjd"><th id="drfjd"></th></form></address>

              <address id="drfjd"></address>

              西塔潘的猜想

              發布時間:2014年12月25日 作者:   消息來源:    閱讀次數:[]

              又稱“拉姆齊二染色定理”,是由英國數理邏輯學家西塔潘于上個世紀90年代提出的一個猜想。在組合數學上,拉姆齊(Ramsey)定理是要解決以下的問題:要找這樣一個最小的數n,使得n個人中必定有k個人相識或l個人互不相識。2011年5月,由北京大學、南京大學和浙江師范大學聯合舉辦的邏輯學術會議在浙江師范大學舉行,中南大學數學科學與計算技術學院酷愛數理邏輯的劉嘉憶的報告給這一懸而未決的公開問題一個否定式的回答,徹底解決了西塔潘的猜想。

              簡介

              1.名師出高徒 

              西塔潘猜想是由英國數理邏輯學家西塔潘于20世紀90年代提出的一個猜想。但定理以弗蘭克·普倫普頓·拉姆齊正式命名,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)。[2] 

              拉姆齊數的數值或上下界 

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

              來源 

              “拉姆齊二染色定理”以弗蘭克·普倫普頓·拉姆齊命名,1930年他在論文On aProblem 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 69 14 18 23 28 36 40 – 434 9 18 25 35 – 41 49 – 61 56 – 84 73 – 115 92 – 1495 1425 43 – 49 58 – 87 80 – 143 101 – 216 125 – 316 143 – 4426 18 35 – 41 58 – 87102 – 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 – 495216 – 1031 282 – 1870 317 – 3583 317 – 60909 36 73 – 115 125 – 316 169 – 780233 – 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內,不一定有一個紅色的三角形或藍色的三角形。每個端點和毗鄰的兩個端點的線是紅色,和其余兩個端點的連線是藍色即可。這個定理的通俗版本就是友誼定理。 

              證明 

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

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

              謎題破解 

              22010年8月,酷愛數理邏輯的劉嘉憶在自學反推數學的時候,第一次接觸到這個問題,并在閱讀大量文獻時發現,海內外不少學者都在進行反推數學中的拉姆齊二染色定理的證明論強度的研究。這是由英國數理邏輯學家西塔潘于上個世紀90年代提出的一個猜想,10多年來許多著名研究者一直努力都沒有解決。2010年年10月的一天,劉嘉憶突然想到利用之前用到的一個方法稍作修改便可以證明這一結論,連夜將這一證明寫出來,投給了數理邏輯國際權威雜志。 

              2011年5月,由北京大學、南京大學和浙江師范大學聯合舉辦的邏輯學術會議在浙江師范大學舉行,還是大三學生的劉嘉憶應邀參加了這次會議,報告了他對目前反推數學中的拉姆齊二染色定理的證明論強度的研究。劉嘉憶的報告給這一懸而未決的公開問題一個否定式的回答,徹底解決了西塔潘的猜想。 

              名師出高徒 

              “中南大學出了個好學生!”一時間,“劉嘉憶”的名字在中國數學界傳開了,他在數理邏輯領域的研究成果備受關注。 

              今年7月初,中國數學界頂尖科學家、中南大學博士生導師侯振挺教授,聽到同行說起了這個消息。并通過給“劉嘉藝”發郵件得知,他就是2008級學校應用數學專業大三學生劉路。 

              侯教授返校后,立即與劉路見了面,并收他做學生。“劉路是個‘本科生’,希望他可以早點讀研。”為此,侯振挺對這匹“千里馬”非常上心,給國內數學界的知名數學家、院士們去電話、發去電郵,希望能夠給教育部說明情況,給予一定的重視。 

              侯振挺說,目前,由中南大學牽頭起草的推薦信,正在依程序辦理中,之后將遞交給教育部。[1]



              上一篇:戴維遜獎
              下一篇:阿貝爾獎

              打印】【收藏】 【關閉

              万博平台