定理定義
在組合數學上，拉姆齊(Ramsey)定理是要解決以下的問題：要找這樣一個最小的數n，使得n個人中必定有k個人相識或l個人互不相識。
拉姆齊理論的核心可以概括成：完全的無序是不可能的。更具體的，Ramsey 理論中 典型的問題是：為了保證在某個集合（或系統）中有某種性質（或結構）一定出現，這個 集合的元素個數應該達到多少？從最初的拉姆齊定理到後來發展出的衆多拉姆齊型定理都表明：一個集合隻要元素數量達到某個臨界值後，一定會出現我們預先定義好的某種 性質或結構。納什之所以自信可以畫出任意的形狀，是因為星星的數量非常巨大，因此可以保證一定會出現想要的形狀。除此之外，我們熟悉的鴿籠原理也是拉姆齊理論的一個例子。
電影《美麗心靈》中有一段非常浪漫的場景：納什和艾麗西亞站在噴泉邊，仰望星空， 艾麗西亞說自己曾數星星數到了 4348 顆，納什笑着回複，咱倆真是一對怪胎。接着，納什 讓艾麗西亞選一個形狀，動物随便什麼都可以。艾麗西亞想了想說，雨傘。納什走到艾麗 西亞背後，拿起她的手，在星空中用星星連出一個雨傘的形狀。艾麗西亞芳心瞬間被俘獲， 于是央求：再來一次，再來一次嘛！來畫個章魚！
姑且不論納什是否做過這麼浪漫的事，也不論納什是否有這樣的本領；假如是真的， 我們想問的是，納什為什麼自信可以用星星連出任意的形狀呢？答案或許藏在一個數學理論中，這就是組合數學中的拉姆齊理論(Ramsey Theory)。
拉姆齊理論的核心可以概括成：完全的無序是不可能的。更具體的，Ramsey 理論中 典型的問題是：為了保證在某個集合（或系統）中有某種性質（或結構）一定出現，這個 集合的元素個數應該達到多少？從最初的拉姆齊定理到後來發展出的衆多拉姆齊型定理都表明：一個集合隻要元素數量達到某個臨界值後，一定會出現我們預先定義好的某種 性質或結構。納什之所以自信可以畫出任意的形狀，是因為星星的數量非常巨大，因此可以保證一定會出現想要的形狀。除此之外，我們熟悉的鴿籠原理也是拉姆齊理論的一個例子。
鴿籠原理傳統的理解是，隻鴿子飛進 個鴿籠，一定會有一個鴿籠裡面至少有兩隻鴿子。如果遵循 Ramsey 理論的思想，我們可以把鴿籠原理換一種方式理解：給定 個鴿籠，如果想要鴿子“同籠”一定發生，那我們至少需要多少隻鴿子？答案是。
再換一套語言來理解鴿籠原理。假設有 種顔色用來給鴿子上色，如果要保證一定出現“同色”鴿子，問至少需要多少隻鴿子？答案還是。
再換一套語言。假設有 兩 個集合，其中集合中有個元素(即勢為)。現在從集合 向集合作映射 ，如果要保證一定會出現，問集合的元素個數至少是多少個？答案還是 。
從這個角度看，鴿籠原理，以至拉姆齊理論其實是在探讨這樣的問題：如何從不确定性中抽取出确定性，或者說如何從混沌（Chaos）中找到秩序（Order）。不确定性是說鴿子飛進鴿籠鴿子的染色方案看成映射，因為不同的映射構成一個随機事件的空間，有些随機事件滿足我們想要的性質，有些則不能；另一方面，如果我們擴張這個空間，則想要的确定性就一定會出現。這個轉變一定會有一個臨界狀态和臨界值，就像水結冰對應的臨界狀态是冰水混合，對應的臨界值是 0°C 一樣。在鴿籠原理中，因為我們想要的性質比較簡單，這個臨界狀态正好是鴿子占滿鴿籠且均勻分布在鴿籠中，因此對應的臨界值是（限制條件的線性函數），這也是為什麼看起來鴿籠原理好像是帶餘除法的應用。
首先看一個代數的例子。我們從 1 依次開始往後寫正整數，假設我們有紅黑兩種顔色的筆，在每個整數寫好的整數上塗上紅色或者黑色。如果想要一定會出現一個長度是3同色的等差數列，問至少要寫到幾？答案是 9。顯然，這裡的臨 界值是 8。
驗證推導
我們用形式語言刻畫圖論，則圖論的語言 ，這裡的表示“邊” , 的理論即圖論是以下兩個句子的句子集：
一個具體的圖即是圖論的一個模型。我們先考察四色定理。
定理 1（四色定理對任意無窮平面圖可以用四種顔色對其結點進行着色，使得相鄰結點都有不同的顔色。
證明對有窮平面圖，已經有 APPellle 和 Haken 在 1976 年證明的有窮平面圖四色定理：每個有窮平面圖都可以用四種顔色着色。我們用預備知識中介紹的概念将這個結論推廣到無窮平面圖。
令 為無窮平面圖，膨脹語言為 ，其中 為引入的四個一元關系符号，分别表示紅、綠、藍、黃，令是膨脹語言中如下的公式
該公式表示可用 四種顔色對平面圖着色。令
則根據有窮平面圖四色定理，有窮可滿足，從而得到又的任一有窮子集有模型，由模型論緊緻性定理，有模型
從而
由引理1，可以同構嵌。
定理推廣
對于任何一個正整數,存在一個最小的正整數,使得對任意一個至少有個頂點的圖,它或者有個頂點的完全子圖,或者有個頂點是獨立集.由此定理易得:設是頂點數的簡單圖,其邊數,且的所有階導出子圖的邊數相等,那麼是完全圖.并給出上述結論的推廣:設是階簡單圖,其邊數,對某個給定的自然數,若的所有階導出子圖的邊數相等,則是完全圖。
定理意義
Ramsey理論的結果通常具有兩個主要特征。首先，它們是非建設性的：它們可能表明存在某種結構，但沒有給出尋找此結構的過程（除了蠻力搜索）。例如，鴿洞原理就是這種形式。其次，盡管拉姆齊理論的結果确實表明足夠大的物體必須一定包含給定的結構，但這些結果的證明通常要求這些物體非常大-呈指數增長或甚至與阿克曼函數一樣快的界線并不罕見。在許多情況下，這些界限是證明的僞像，尚不清楚是否可以對其進行實質性的改進。在其他情況下，已知任何邊界都必須非常大，有時甚至比任何原始遞歸函數還要大；有關示例，請參見Paris-Harrington定理。格雷厄姆數是認真的數學證明中使用的最大數，是與拉姆齊理論有關的問題的上限。
Ramsey理論中的定理通常是三種類型之一。許多定理以Ramsey定理本身為模型，它們斷言在一個大型結構化對象的每個分區中，其中一個類必然包含一個大型結構化子對象，但沒有提供有關這是哪個類的信息。有時，出現此類Ramsey類型結果的原因是最大的分區類始終包含所需的子結構。根據圖蘭定理，這種結果稱為密度結果或圖蘭類型結果。著名的例子包括Szemerédi定理，它是對van der Waerden定理的強化，以及Hales-Jewett定理的密度形式。
拉姆齊二染色定理
拉姆齊二染色定理是由英國數理邏輯學家西塔潘（Seetapun）于20世紀90年代提出的一個猜想。十多年來，許多著名研究者一直努力都沒有解決。今年5月，由北京大學等聯合舉辦的邏輯學術會議上，還是大三的劉嘉憶報告了他對目前反推數學中的拉姆齊(Ramsly)二染色定理的證明論強度的研究。這是由英國數理邏輯學家Seetapun于上個世紀90年代提出的一個猜想，十多年來，許多著名研究者一直努力都沒有解決。劉嘉憶的報告給這一懸而未決的公開問題一個否定式的回答，徹底解決了Seetapun的猜想。繼今年上半年他攻克一個十多年懸而未決國際數學難題後，不久前在美國芝加哥大學結束的數理邏輯學術會議上，他作為亞洲高校唯一一位代表在會上做了40分鐘報告，報告了他在數理邏輯方面的研究成果，語驚四座。
