西塔潘猜想
西塔潘猜想是由英國數理邏輯學家西塔潘於上個世紀90年代提出的一個反推數學領域關於拉姆齊二染色定理證明強度的猜想。在組合數學上，拉姆齊（Ramsey）定理是要解決以下的問題：要找這樣一個最小的數n，使得n個人中必定有k個人相識或l個人互不相識。2011年5月，由北京大學、南京大學和浙江師範大學聯合舉辦的邏輯學術會議在浙江師範大學舉行，中南大學數學科學與計算技術學院酷愛數理邏輯的劉嘉憶的報告給這一懸而未決的公開問題一個否定式的回答，徹底解決了西塔潘的猜想,證明了R(3,3)=6。也稱為拉姆齊二染色定理。
基本介紹
中文名：西塔潘猜想提出人物：西塔潘提出時間：上個世紀90年代提出地點：劍橋大學
猜想簡介,定義,相關來源,證明,謎解,
猜想簡介西塔潘猜想是由英國數理邏輯學家西塔潘於20世紀90年代提出的一個猜想。但定理以弗蘭克·普倫普頓·拉姆齊正式命名，1930年其在論文One 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)的值，那么人類應當全力發展軍事力量。相關來源“拉姆齊二染色定理”以弗蘭克·普倫普頓·拉姆齊命名。拉姆齊數的定義拉姆齊數，用圖論的語言有兩種描述：對於所有的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中，必定有一個顏色為e1l1階子完全圖，或有一個顏色為e2l2階子完全圖……或有一個顏色為erlr階子完全圖。符合條件又最少的數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的順序改變並不改變拉姆齊的數值）我們應該知道在反推數學中，研究的其實是二階算術的各個子系統以及它們的強度關係，而最重要的是被稱為 Big Five的五個子系統其中的三個 RCA 0 , WKL 0 , ACA 0，其中 WKL 0 是基本系統 RCA 0 添加弱柯尼希定理的系統，而 RCA 0 添加拉姆齊二染色定理的系統被稱為 RT2 2。經過若干數學家的研究，他們發現了一些子系統間存在強弱的比較關係：和 RT2 2 形式接近的 RT3 2 比 ACA 0 要強，而 RT2 2 則不比 ACA 0 強等等，從這些結果，他們隱約認為 RT2 2 和 WKL 0 的強度是可以比較的，1995年英國數理邏輯學家西塔潘在一篇論文（On the Strength of Ramsey’s Theorem）中發現WKL_0並不強於 RT2 2 ，於是他猜測可能 RT2 2 要強於 WKL 0 。這一猜想引發了大量研究，困擾了許多數學家十多年之久。證明R(3,3)等於6的證明 證明：在一個K6的完全圖內，每邊塗上紅或藍色，必然有一個紅色的三角形或藍色的三角形。任意選取一個端點P，它有5條邊和其他端點相連。根據鴿巢原理，5條邊的顏色至少有3條相同，不失一般性設這種顏色是紅色。在這3條邊除了P以外的3個端點，它們互相連結的邊有3條。若這3條邊中任何一條是紅色，這條邊的兩個端點和P相連的2邊便組成一個紅色三角形。若這3條邊中任何一條都不是紅色，它們必然是藍色，因此，它們組成了一個藍色三角形。而在K5內，不一定有一個紅色的三角形或藍色的三角形。每個端點和毗鄰的兩個端點 的線是紅色，和其餘兩個端點的連線是藍色即可。這個定理的通俗版本就是友誼定理。謎解2010年8月，酷愛數理邏輯的劉路（後改名為劉嘉憶）在自學反推數學的時候，第一次接觸到這個問題，並在閱讀大量文獻時發現，海內外不少學者都在進行反推數學中的拉姆齊二染色定理的證明論強度的研究。這是由英國數理邏輯學家西塔潘於上個世紀90年代提出的一個猜想，10多年來許多著名研究者一直努力都沒有解決。2010年10月的一天，劉路突然想到利用之前用到的一個方法稍作修改便可以證明這一結論，連夜將這一證明寫出來，投給了數理邏輯國際權威雜誌。2011年5月，由北京大學、南京大學和浙江師範大學聯合舉辦的邏輯學術會議在浙江師範大學舉行，還是大三學生的劉路應邀參加了這次會議，報告了他對反推數學中的拉姆齊二染色定理的證明論強度的研究。劉嘉憶的報告給這一懸而未決的公開問題一個否定式的回答，徹底解決了西塔潘的猜想。
相關詞條
西塔潘猜想西塔潘猜想是由英國數理邏輯學家西塔潘於上個世紀90年代提出的一個反推數學領域關於拉姆齊二染色定理證明強度的猜想。在組合數學上,拉姆齊(Ramsey)定理是要解決以下...
西塔潘西塔潘猜想是由英國數理邏輯學家西塔潘於上個世紀90年代提出的一個反推數學領域關於拉姆齊二染色定理證明強度的猜想。...
數學猜想數學猜想有的被驗證為正確的(如費馬猜想、卡塔蘭猜想、龐加萊猜想等),並成為...西塔潘猜想(中南大學2008級 劉路 證明)開放問題(正在驗證)Abc猜想...
友誼定理西塔潘猜想還有一個雅稱,叫“友誼定理”(Friendship theorem)也叫“政治家定理”或“交際花定理”,友誼定理緣於三角戀,故事中的三角戀是兩個女生與一個男生,或者...
劉嘉憶本名劉路,中南大學數學科學與計算技術學院2008級本科生,在大學三年級時獨立解決了英國數理邏輯學者西塔潘提出的一個猜想,在國內引起關注。2011年10月,中國科學院...
王驍威這是一個原本被視為又一個劉路(22歲破解“西塔潘猜想”,現為中南大學學生)的年輕人。剛被媒體報導時,外界發現兩人有許多相似之處:同樣生於1990年,同樣並非優等...
影響世界華人盛典頒授給青少年的希望之星大獎,今年由破解了一道困擾數理邏輯學20年的難題“西塔潘猜想”的中南大學學生劉路獲得。延續前兩年在華人盛典頒獎禮上特設的緬懷環節,今年的...
中南大學鐵道學院被奉為小天才的劉路,解決了“數十年來懸而未決的‘西塔潘猜想’”, 22歲晉升為教授級研究員。學院還先後獲得了1項國家自然科學三等獎、2項國家科技進步一等獎、...
我和數學有約——趣味數學及算法解析第4章著名猜想家 414.1西塔潘猜想破解了嗎 414.2四色定理 434.3黎曼猜想 464.4霍奇猜想 474.5龐加萊猜想 484.6楊-米爾斯存在性和質量缺口 50...
我們中國人2012他叫劉路,是中南大學的一名大學生,2010年,他因解決了國際數學難題“西塔潘猜想”而引發各界關注。2012年3月20日,中南大學破格聘任他為教授級研究員。年僅22歲的...
圖解中考作文素材22歲大學生破解西塔潘猜想 第三章 經典哲理篇 怎樣做好一盞燈 忠告要像螺釘一樣 “放”的學問 杯子與水 毒蛇草的專長 不抓老鼠的貓鼬 速度決定成功...
2012中國科學年度新聞人物“西塔潘猜想”已提出17年,國際上很多人試圖去解決,均未成功。劉路是中南大學數學與統計學院2012級博士研究生,也是中國最年輕的教授。在大三時,他憑藉多年的積累...
熱門詞條
早乙女阿爾特
FV2
素萃
窗簾軌道
JINS
男女糾察隊
MSM
奇米
乾眼症
盧惠光
牙齒
follow
錯斬崔寧
天體營
五行蔬菜湯
Circle：相連的兩個世界
原來愛
從前有座靈劍山
東方出版社
關鍵字
甲醛檢測
偉人
老雪花齋
On The Floor
環球影城
門禁
炸皮蛋
獅頭山風景區