西塔潘猜想又稱(chēng)“拉姆齊二染色定理”，是由英國(guó)數(shù)理邏輯學(xué)家西塔潘于20世紀(jì)90年代提出的一個(gè)猜想。在組合數(shù)學(xué)上，拉姆齊（Ramsey）定理是要解決以下的問(wèn)題：要找這樣一個(gè)最小的數(shù)n，使得n個(gè)人中必定有k個(gè)人相識(shí)或l個(gè)人互不相識(shí)。 

這個(gè)定理以弗蘭克·普倫普頓·拉姆齊命名，1930年他在論文On a Problem in Formal Logic（《形式邏輯上的一個(gè)問(wèn)題》）證明了R(3,3)=6。拉姆齊數(shù)的定義拉姆齊數(shù)，用圖論的語(yǔ)言有兩種描述：對(duì)于所有的N頂圖，包含k個(gè)頂?shù)膱F(tuán)或l個(gè)頂?shù)莫?dú)立集。具有這樣性質(zhì)的最小自然數(shù)N就稱(chēng)為一個(gè)拉姆齊數(shù)，記作R(k,l)；在著色理論中是這樣描述的：對(duì)于完全圖Kn的任意一個(gè)2邊著色(e1,e2)，使得Kn[e1]中含有一個(gè)k階子完全圖，Kn[e2]含有一個(gè)l階子完全圖，則稱(chēng)滿(mǎn)足這個(gè)條件的最小的n為一個(gè)拉姆齊數(shù)。（注意：Ki按照?qǐng)D論的記法表示i階完全圖）拉姆齊證明，對(duì)與給定的正整數(shù)數(shù)k及l(fā)，R(k,l)的答案是唯一和有限的。拉姆齊數(shù)亦可推廣到多于兩個(gè)數(shù)：對(duì)于完全圖Kn的每條邊都任意涂上r種顏色之一，分別記為e1,e2,e3,...,er，在Kn中，必定有個(gè)顏色為e1的l1階子完全圖，或有個(gè)顏色為e2的l2階子完全圖……或有個(gè)顏色為er的lr階子完全圖。符合條件又最少的數(shù)n則記為R(l1,l2,l3,...,lr;r)?！±俘R數(shù)的數(shù)值或上下界已知的拉姆齊數(shù)非常少，保羅·艾狄胥曾以一個(gè)故事來(lái)描述尋找拉姆齊數(shù)的難度：“想像有隊(duì)外星人軍隊(duì)在地球降落，要求取得R(5,5)的值，否則便會(huì)毀滅地球。在這個(gè)情況，我們應(yīng)該集中所有電腦和數(shù)學(xué)家嘗試去找這個(gè)數(shù)值。若它們要求的是R(6,6)的值，我們要嘗試毀滅這班外星人了。”顯然易見(jiàn)的公式： 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的順序改變并不改變拉姆齊的數(shù)值）?！,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的證明證明：在一個(gè)K6的完全圖內(nèi)，每邊涂上紅或藍(lán)色，必然有一個(gè)紅色的三角形或藍(lán)色的三角形。任意選取一個(gè)端點(diǎn)P，它有5條邊和其他端點(diǎn)相連。根據(jù)鴿巢原理，3條邊的顏色至少有兩條相同，不失一般性設(shè)這種顏色是紅色。在這3條邊除了P以外的3個(gè)端點(diǎn)，它們互相連結(jié)的邊有3條。若這3條邊中任何一條是紅色，這條邊的兩個(gè)端點(diǎn)和P相連的2邊便組成一個(gè)紅色三角形。若這3條邊中任何一條都不是紅色，它們必然是藍(lán)色，因此，它們組成了一個(gè)藍(lán)色三角形。而在K5內(nèi)，不一定有一個(gè)紅色的三角形或藍(lán)色的三角形。每個(gè)端點(diǎn)和毗鄰的兩個(gè)端點(diǎn)的線(xiàn)是紅色，和其余兩個(gè)端點(diǎn)的連線(xiàn)是藍(lán)色即可。這個(gè)定理的通俗版本就是友誼定理。 

數(shù)理邏輯是研究推理的數(shù)學(xué)分支。它使用數(shù)學(xué)的方法，即一套符號(hào)體系來(lái)研究推理前提和結(jié)論之間的形式關(guān)系，故也稱(chēng)符號(hào)邏輯。

2010年8月，酷愛(ài)數(shù)理邏輯的劉嘉憶在自學(xué)反推數(shù)學(xué)的時(shí)候，第一次接觸到這個(gè)問(wèn)題，并在閱讀大量文獻(xiàn)時(shí)發(fā)現(xiàn)，海內(nèi)外不少學(xué)者都在進(jìn)行反推數(shù)學(xué)中的拉姆齊二染色定理的證明論強(qiáng)度的研究。這是由英國(guó)數(shù)理邏輯學(xué)家西塔潘于上個(gè)世紀(jì)90年代提出的一個(gè)猜想，多年來(lái)許多著名研究者一直努力都沒(méi)有解決。

同年10月的一天，劉嘉憶突然想到利用之前用到的一個(gè)方法稍作修改便可以證明這一結(jié)論，他隨即連夜將證明寫(xiě)出，投給了數(shù)理邏輯國(guó)際權(quán)威雜志《符號(hào)邏輯雜志》。

2011年5月，由北大、南京大學(xué)和浙江師大聯(lián)合舉辦的邏輯學(xué)術(shù)會(huì)議在浙江師范大學(xué)舉行，還是大三學(xué)生的劉嘉憶應(yīng)邀參加了這次會(huì)議，報(bào)告了他對(duì)目前反推數(shù)學(xué)中的拉姆齊二染色定理的證明論強(qiáng)度的研究。劉嘉憶的報(bào)告給了這一懸而未決的公開(kāi)問(wèn)題一個(gè)否定式的回答，徹底解決了西塔潘的猜想。

　2011年9月16日，美國(guó)芝加哥大學(xué)數(shù)理邏輯學(xué)術(shù)會(huì)議上，云集了來(lái)自歐美的許多數(shù)理邏輯專(zhuān)家、學(xué)者。大會(huì)邀請(qǐng)了12位專(zhuān)家、學(xué)者作學(xué)術(shù)報(bào)告，劉嘉憶作為亞洲高校唯一一位代表在會(huì)上作了40分鐘報(bào)告。他在數(shù)理邏輯方面的研究成果，讓與會(huì)專(zhuān)家、學(xué)者對(duì)這位來(lái)自中國(guó)的“80后”投上贊許的目光。劉嘉憶表示，他投給《美國(guó)數(shù)學(xué)會(huì)匯刊》的論文獲得威士康星大學(xué)、伯克利大學(xué)等幾位教授很高的評(píng)價(jià)，有望公開(kāi)發(fā)表。