拉姆齐定理
在組合數學上，拉姆齐定理（），又称拉姆齐二染色定理，斷言對任意正整數formula_1和formula_2，若一個聚會的人數formula_3足夠大，則無論相识關係如何，必定有formula_1个人相识或formula_2个人互不相识。給定formula_6時，保證前述結論的最小formula_3值稱為拉姆齊數formula_8，其值取決於formula_6。用圖論術語複述：若將足夠大的完全圖各邊染紅藍兩色，則不論如何染，必定有紅色的formula_1階完全圖或藍色的formula_2階完全圖。
拉姆齊定理是組合數學的重要結論，以弗兰克·普伦普顿·拉姆齐命名。他在1930年論文證明此定理最初的版本，開創現稱拉姆齊理論的組合理論分支。拉姆齊理論的主題是從「無序」尋找「規律」，希望找出某數學結構中，存在規律子結構的一般條件。在拉姆齊定理的圖論表述中，此「規律子結構」是同色集（），即頂點集的子集，其中各邊皆染成同一顏色。
拉姆齊定理不止一條，前述版本的若干引伸仍稱拉姆齊定理。例如，可以將二染色推廣至更多種色，此時定理斷言：對任意色數formula_12，和任意正整數formula_13，必有某數formula_14，使formula_14階的完全圖各邊不論如何染formula_12色，仍必可找到某formula_17（介於formula_18至formula_12）和某formula_20階完全子圖，其各邊皆染第formula_17色。可見拉姆齐二染色定理是formula_22的特例（同時取formula_23）。
在6個頂點的完全圖formula_24內，每邊塗上紅或藍色。欲證必然有一個紅色的三角形或藍色的三角形。
以上論證對一切染色法都適用，所以formula_24的任何二染色皆有同色formula_32，換言之formula_33。这个定理的通俗版本稱為朋友與陌路人定理。
另一種證法是算兩次：考慮「異色角」的數目，即滿足formula_34為紅而formula_35為藍的有序三頂點組formula_36的個數。若先固定中間的頂點formula_37，則對應三元組的數目可能是 所以，至多是formula_41，而formula_37本身有6種可能，異色角的總數至多是formula_43。但是，對於三邊不完全同色的三角形，恰好有兩隻異色角，所以，至多有formula_44個異色三角形。考慮到6個頂點組成formula_45個三角形，至少有兩個是同色三角形，再次得到formula_33的結論。
反之，將formula_47二染色，不一定有同色的三角形。此構造在同構意義下唯一，如下圖所示：將五個頂點排成一圈，每個端點和毗鄰的兩個端點之間的連線染紅色，與其餘兩個端點的連線染藍色，則不產生同色三角形。所以，formula_48。
1953年普特南數學競賽考過formula_49。1947年匈牙利屈爾沙克·約瑟夫數學比賽（）亦然。
多色拉姆齊數就是用三種或更多顏色的拉姆齊數。若不考慮對稱的情況，僅有兩個非平凡的多色拉姆齊數為已知：formula_50和formula_51。
設將某完全圖的邊染紅綠藍三色，而無同色三角形。選任一頂點formula_52，考慮以紅邊與formula_52相連的各點，組成formula_52的「紅鄰域」。紅鄰域之內不能再有任何紅邊，否則該紅邊與formula_52一同組成紅色三角形。所以紅鄰域內的邊衹用藍綠兩色。由上節formula_48，formula_52的紅鄰域最多衹有5個頂點，否則有藍或綠的同色三角形。同理，formula_52的綠鄰域和藍鄰域，各有至多5個頂點，但圖中每個頂點，或為formula_52本身，或屬formula_52的某色鄰域，所以全圖至多formula_61個頂點。故formula_62。
欲證formula_63，現需用三種顏色畫出16個頂點的完全圖，而不產生同色三角形。若不辨同構之異，則恰有兩種畫法，分別稱為「無扭」（）和「有扭」（）染法，見上圖。 formula_64的有扭或無扭染色中，選任一顏色，該色邊組成的子圖都是。
對較少頂點的完全圖，已知formula_65亦衹得兩種染三色的方法無同色三角形，分別來自formula_64的兩種染法，刪去任意一個頂點。formula_67則有115種方法染三色而無同色三角形，但此數不僅不辨圖同構（頂點的置換），還不辨顏色的置換。
拉姆齐数，用图论的语言有两种描述：
拉姆齐证明，对与给定的正整數数"k"及"l"，R("k","l")的答案是唯一和有限的。
拉姆齐數亦可推廣到多於兩個數：
已知的拉姆齐數非常少，保羅·艾狄胥曾以一個譬喻來描述尋找拉姆齐數的難度：「想像有隊外星人軍隊在地球降落，要求取得R(5,5)的值，否則便會毀滅地球。在這個情況，我們應該集中所有電腦和數學家嘗試去找這個數值。若他們要求的是R(6,6)的值，我們要嘗試毀滅這班外星人了。」
顯然易見的公式： R(0,"s")=0， R(1,"s")=1， R(2,"s")="s"， formula_83（將formula_84的順序改變並不改變拉姆齐的數值）。
有不定期更新的動態綜述，介紹拉姆齊數的研究成果。
拉姆齊數滿足不等式formula_85。由此，利用數學歸納法，可以證明
上述結果歸功於艾狄胥和塞凱賴什。當formula_87時，用史特靈公式化成： 其中誤差項"o" (1)，當formula_89趨向於無窮時，趨向formula_90。
下界方面，1947年艾狄胥首創，證明 雖然上下界皆是指數形式，但兩者底數不同，實際大小相差甚遠，如formula_92時，給出的界是formula_93。不過，截至2021年，上下界的底數仍毫無改進，依舊是formula_94和formula_95，僅有較低階項的改進。而且，下界依賴非構造性的概率方法，未有任何確切構造能給出指數下界。暫時所知最佳結果為：
分別為和所證。
至於非對角拉姆齊數formula_97，已知其增長級別為formula_98；等價說法是，formula_3個頂點且的圖formula_100，獨立數formula_101的最小值用大Θ符號表示成
formula_97的上界由、、塞迈雷迪證出，而formula_98級的下界原先由（音譯）證明，其後格里菲斯、、菲斯·庞蒂韦罗斯三人和、兩人藉分析「無三角形過程」，分別將下界獨立改進至
一般的非對角拉姆齊數formula_106，當formula_89固定而formula_108增大時，已知最優的上下界為
分別歸功於波曼、基瓦什兩人和奧伊陶伊、科姆洛什、塞迈雷迪三人。
本定理可引伸適用於無窮圖，同樣稱為拉姆齊定理。與有限圖的拉姆齊定理相提並論時，或稱無窮拉姆齊定理（）以作區分。
設formula_110為無窮集，以formula_111表示其兩兩所連邊的集合（即formula_110全體二元子集組成的族），每邊染成formula_12色之一。則存在同色無窮階完全圖，即有無窮子集formula_114，其邊集formula_115同色。 證明：取任一formula_116。自formula_117引出無窮多條邊，必有某色formula_118出現無窮多次。記formula_119為該些邊另一端點的集合。又取任一formula_120，同樣自formula_121有無窮多條邊引至formula_122，故必有某色formula_123及無窮子集formula_124，使formula_121引至formula_126的各邊皆染formula_123色。
餘可類推，得到一列互異的元素formula_128及一列顏色formula_129。由於僅得有限多種色，必有顏色出現無窮多次，即有formula_130對於無窮序列formula_131成立。此時，有formula_132為無窮子集，且其元素兩兩連邊同色（因為邊formula_133所染為formula_134色），證畢。
本定理對於超圖（即formula_111換成formula_136）亦成立。
關於無窮圖的二染色，是較強的結果，但其中兩種顏色不對等。定理斷言，任意無窮圖（頂點數不必可數）的邊若染紅藍兩色，則或有可數無窮大的紅色完全子圖，或有與原圖同樣大的藍色完全子圖。
運用反證法，可以證明無窮拉姆齊定理推出有限拉姆齊定理。 反設有限拉姆齊定理不成立，即某個拉姆齊數不存在，則有整數formula_12和formula_138滿足：對任意正整數formula_1，完全圖formula_140皆有某種染formula_12色的方案，而不產生同色的formula_138元子集。以formula_143表示此種方案的集合。
對任意formula_1，可將formula_145中任意一種染色限制到子圖formula_140（即刪去頂點formula_147），不會額外產生同色的formula_138元子集，所以所得的染色仍在formula_143中。formula_143中，某些染色是以上述方式，由formula_145的染色限制而成，此種染色構成formula_143的子集，記為formula_153。由假設，formula_145非空，所以formula_153亦非空。
同樣，formula_156元素的限制必屬formula_153，故可定義formula_158為此種限制所得染色法的集合，其不為空。類推對所有正整數formula_159定義formula_160。
現對每個正整數formula_1，有formula_162，且逐個集合非空。又formula_143為有限集，因為由乘法原理，全體染色方案，不論是否有同色formula_138元集，總數是formula_165。由此，整個序列的交集formula_166非空。又每個formula_167的元素來自formula_168某元素的限制，可知formula_169每個元素都來自formula_170元素的限制，從而由formula_169的染色出發，可以延拓成formula_170的染色，並可重複，直至得到無窮圖formula_173的染色，而無同色formula_138元集，與無窮拉姆齊定理矛盾。
以拓撲學觀之，此為標準的緊論證（），相當於考慮全體染色的拓撲空間formula_175，而由吉洪諾夫定理，其為若干個有限（從而緊）空間formula_176之積，所以仍為緊。而條件「在子圖formula_140上不產生同色formula_138元集」，描述該空間的一個閉開集，所以有限交非空推出全體交非空。
定理亦可推廣至超图。一個formula_179均勻超圖（或formula_179超圖）就是將圖的邊由二元子集換成formula_179元子集。超圖拉姆齊定理敍述如下：
對任意正整數formula_179和formula_12，以及任意正整數formula_13，存在拉姆齊數formula_185，使得formula_185階完全formula_179超圖的各邊，不論如何染formula_12種色，必存在formula_17令圖中可找出某個衹染formula_17色的formula_20階完全formula_179超圖。
此定理一般對formula_179歸納證出，formula_194的初始情況正如前文。
亦可定義有向圖的拉姆齊數，最早由提出。設formula_195為最小的正整數formula_196，使得formula_196階完全圖中，若為每邊賦兩種定向之一（所得有向圖稱為），則必有無圈的formula_3階循環賽圖 。
此前formula_199定義為保證formula_200階完全無向圖染兩色會有同色完全formula_3階子圖的最小formula_200值，可見formula_195是formula_199的有向類比：兩種顏色現換成邊的兩種方向，而「同色」換成「全部邊方向統一」（所以無圈）。
已知formula_205，formula_206，formula_207，formula_208，formula_209，formula_210，formula_211，formula_212。