西塔潘猜想

西塔潘猜想是由英國數理邏輯學家西塔潘於上個世紀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 ₀ , WKL ₀ , ACA _0，其中 WKL ₀ 是基本系統 RCA ₀ 添加弱柯尼希定理的系統，而 RCA ₀ 添加拉姆齊二染色定理的系統被稱為 RT² ₂。經過若干數學家的研究，他們發現了一些子系統間存在強弱的比較關係：和 RT² ₂ 形式接近的 RT³ ₂ 比 ACA ₀ 要強，而 RT² ₂ 則不比 ACA ₀ 強等等，從這些結果，他們隱約認為 RT² ₂ 和 WKL ₀ 的強度是可以比較的，1995年英國數理邏輯學家西塔潘在一篇論文（On the Strength of Ramsey’s Theorem）中發現WKL_0並不強於 RT² ₂ ，於是他猜測可能 RT² ₂ 要強於 WKL ₀ 。

這一猜想引發了大量研究，困擾了許多數學家十多年之久。

證明

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