拉姆齐定理

在組合數學上，拉姆齐定理（英語：Ramsey's theorem），又称拉姆齐二染色定理，斷言對任意正整數${\displaystyle k}$和${\displaystyle l}$，若一個聚會的人數${\displaystyle n}$足夠大，則無論相识關係如何，必定有${\displaystyle k}$个人相识或${\displaystyle l}$个人互不相识。給定${\displaystyle k,l}$時，保證前述結論的最小${\displaystyle n}$值稱為拉姆齊數${\displaystyle R(k,l)}$，其值取決於${\displaystyle k,l}$。用圖論術語複述：若將足夠大的完全圖各邊染紅藍兩色，則不論如何染，必定有紅色的${\displaystyle k}$階完全圖或藍色的${\displaystyle l}$階完全圖。^{[註 1]}

拉姆齊定理是組合數學的重要結論，以弗兰克·普伦普顿·拉姆齐命名。他在1930年論文《論形式邏輯的一個問題》^[1]證明此定理最初的版本，開創現稱拉姆齊理論的組合理論分支。拉姆齊理論的主題是從「無序」尋找「規律」，希望找出某數學結構中，存在規律子結構的一般條件。在拉姆齊定理的圖論表述中，此「規律子結構」是同色集（monochromatic set），即頂點集的子集，其中各邊皆染成同一顏色。

拉姆齊定理不止一條，前述版本的若干引伸仍稱拉姆齊定理。例如，可以將二染色推廣至更多種色，此時定理斷言：對任意色數${\displaystyle c}$，和任意正整數${\displaystyle n_{1},n_{2},\ldots ,n_{c}}$，必有某數${\displaystyle R(n_{1},\ldots ,n_{c})}$，使${\displaystyle R(n_{1},\ldots ,n_{c})}$階的完全圖各邊不論如何染${\displaystyle c}$色，仍必可找到某${\displaystyle i}$（介於${\displaystyle 1}$至${\displaystyle c}$）和某${\displaystyle n_{i}}$階完全子圖，其各邊皆染第${\displaystyle i}$色。可見拉姆齐二染色定理是${\displaystyle c=2}$的特例（同時取${\displaystyle n_{1}=k,n_{2}=l}$）。

例

R (3, 3) = 6

 

在6個頂點的完全圖${\displaystyle K_{6}}$ 內，每邊塗上紅或藍色。欲證必然有一個紅色的三角形或藍色的三角形。

• 任意選取一個端點${\displaystyle P}$ ，它有5條邊和其他端點相連。
• 根據鴿巢原理，5條邊染兩種顏色，至少有3邊顏色相同，不失一般性設這種顏色是紅色，又設該三邊為${\displaystyle PA,PB,PC}$ 。
• ${\displaystyle A,B,C}$ 三個頂點，互相連結的邊有${\displaystyle AB,BC,CA}$ 三條。
  • 若這3條邊中任何一條是紅色，這條邊的兩個端點和${\displaystyle P}$ 便組成一個紅色三角形。
  • 若這3條邊中沒有紅邊，則都是藍色，因此，${\displaystyle ABC}$ 是藍色三角形。

以上論證對一切染色法都適用，所以${\displaystyle K_{6}}$ 的任何二染色皆有同色${\displaystyle K_{3}}$ ，換言之${\displaystyle R(3,3)\leq 6}$ 。这个定理的通俗版本稱為朋友與陌路人定理。

另一種證法是算兩次：考慮「異色角」的數目，即滿足${\displaystyle xy}$ 為紅而${\displaystyle yz}$ 為藍的有序三頂點組${\displaystyle (x,y,z)}$ 的個數。若先固定中間的頂點${\displaystyle y}$ ，則對應三元組的數目可能是

• ${\displaystyle 0\times 5=0}$ （若其全部邊染同色）；
• ${\displaystyle 1\times 4=4}$ （若有四邊染某色，另一邊不同色）；或
• ${\displaystyle 2\times 3=6}$ （若有三邊染某色，另兩邊染另一色）。

所以，至多是${\displaystyle 6}$ ，而${\displaystyle y}$ 本身有6種可能，異色角的總數至多是${\displaystyle 6\times 6=36}$ 。但是，對於三邊不完全同色的三角形，恰好有兩隻異色角，所以，至多有${\displaystyle 18}$ 個異色三角形。考慮到6個頂點組成${\displaystyle {\binom {6}{3}}=20}$ 個三角形，至少有兩個是同色三角形，再次得到${\displaystyle R(3,3)\leq 6}$ 的結論。

反之，將${\displaystyle K_{5}}$ 二染色，不一定有同色的三角形。此構造在同構意義下唯一，如下圖所示：將五個頂點排成一圈，每個端點和毗鄰的兩個端點之間的連線染紅色，與其餘兩個端點的連線染藍色，則不產生同色三角形。所以，${\displaystyle R(3,3)=6}$ 。

 

1953年普特南數學競賽考過${\displaystyle R(3,3)\leq 6}$ 。^[2]1947年匈牙利屈爾沙克·約瑟夫數學比賽（匈牙利語：Kürschák József Matematikai Tanulóverseny）亦然。^[3]

R (3, 3, 3) = 17

• 僅有兩種方法將16個頂點之間的邊染三種顏色而無同色三角形
•  

  無扭的

•  

  有扭的

多色拉姆齊數就是用三種或更多顏色的拉姆齊數。若不考慮對稱的情況，僅有兩個非平凡的多色拉姆齊數為已知：${\displaystyle R(3,3,3)=17}$ 和${\displaystyle R(3,3,4)=30}$ 。^[4]

設將某完全圖的邊染紅綠藍三色，而無同色三角形。選任一頂點${\displaystyle v}$ ，考慮以紅邊與${\displaystyle v}$ 相連的各點，組成${\displaystyle v}$ 的「紅鄰域」。紅鄰域之內不能再有任何紅邊，否則該紅邊與${\displaystyle v}$ 一同組成紅色三角形。所以紅鄰域內的邊衹用藍綠兩色。由上節${\displaystyle R(3,3)=6}$ ，${\displaystyle v}$ 的紅鄰域最多衹有5個頂點，否則有藍或綠的同色三角形。同理，${\displaystyle v}$ 的綠鄰域和藍鄰域，各有至多5個頂點，但圖中每個頂點，或為${\displaystyle v}$ 本身，或屬${\displaystyle v}$ 的某色鄰域，所以全圖至多${\displaystyle 1+5+5+5=16}$ 個頂點。故${\displaystyle R(3,3,3)\leq 17}$ 。

欲證${\displaystyle R(3,3,3)=17}$ ，現需用三種顏色畫出16個頂點的完全圖，而不產生同色三角形。若不辨同構之異，則恰有兩種畫法，分別稱為「無扭」（untwisted）和「有扭」（twisted）染法，見上圖。

 

克萊布殊圖（英语：Clebsch graph）

${\displaystyle K_{16}}$ 的有扭或無扭染色中，選任一顏色，該色邊組成的子圖都是克萊布殊圖（英语：Clebsch graph）。

對較少頂點的完全圖，已知${\displaystyle K_{15}}$ 亦衹得兩種染三色的方法無同色三角形，分別來自${\displaystyle K_{16}}$ 的兩種染法，刪去任意一個頂點。${\displaystyle K_{14}}$ 則有115種方法染三色而無同色三角形，但此數不僅不辨圖同構（頂點的置換），還不辨顏色的置換。

拉姆齐数

定義

拉姆齐数，用图论的语言有两种描述：

1. 对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；
2. 在着色理论中是这样描述的：对于完全圖${\displaystyle K_{n}}$ 的任意一个2边着色${\displaystyle (e_{1},e_{2})}$ ，使得${\displaystyle K_{n}[e_{1}]}$ 中含有一個k阶子完全图，${\displaystyle K_{n}[e_{2}]}$ 含有一個l阶子完全图，则称满足这个条件的最小的n为一个拉姆齐数。（注意：${\displaystyle K_{i}}$ 按照图论的记法表示i阶完全图）

拉姆齐证明，对与给定的正整數数k及l，R(k,l)的答案是唯一和有限的。

拉姆齐數亦可推廣到多於兩個數：

对于完全圖${\displaystyle K_{n}}$ 的每條邊都任意塗上r種顏色之一，分別記為${\displaystyle e_{1},e_{2},e_{3},...,e_{r}}$ ，在${\displaystyle K_{n}}$ 中，必定有個顏色為${\displaystyle e_{1}}$ 的${\displaystyle l_{1}}$ 阶子完全图，或有個顏色為${\displaystyle e_{2}}$ 的${\displaystyle l_{2}}$ 阶子完全图……或有個顏色為${\displaystyle e_{r}}$ 的${\displaystyle l_{r}}$ 阶子完全图。符合條件又最少的數n則記為${\displaystyle R(l_{1},l_{2},l_{3},...,l_{r})}$ 。

數值或上下界

已知的拉姆齐數非常少，保羅·艾狄胥曾以一個譬喻來描述尋找拉姆齐數的難度：「想像有隊外星人軍隊在地球降落，要求取得R(5,5)的值，否則便會毀滅地球。在這個情況，我們應該集中所有電腦和數學家嘗試去找這個數值。若他們要求的是R(6,6)的值，我們要嘗試毀滅這班外星人了。」^{[來源請求]}

顯然易見的公式： R(0,s)=0， R(1,s)=1， R(2,s)=s， ${\displaystyle \mathrm {R} (l_{1},l_{2},l_{3},...,l_{r})=R(l_{2},l_{1},l_{3},...,l_{r})=R(l_{3},l_{1},l_{2},...,l_{r})}$ （將${\displaystyle l_{i}}$ 的順序改變並不改變拉姆齐的數值）。

拉姆齐数R(r, s)的值/已知上下界 （OEIS數列A212954）

s r	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2		2	3	4	5	6	7	8	9	10
3			6	9	14	18	23	28	36	40–42
4				18	25^[5]	36–41	49–61	59^[6]–84	73–115	92–149
5					43–48	58–87	80–143	101–216	133–316	149^[6]–442
6						102–165	115^[6]–298	134^[6]–495	183–780	204–1171
7							205–540	217–1031	252–1713	292–2826
8								282–1870	329–3583	343–6090
9									565–6588	581–12677
10										798–23556

組合電子期刊（英语：Electronic Journal of Combinatorics）有不定期更新的動態綜述，介紹拉姆齊數的研究成果。^[4]

漸近性質

拉姆齊數滿足不等式${\displaystyle R(r,s)\leq R(r-1,s)+R(r,s-1)}$ 。由此，利用數學歸納法，可以證明

${\displaystyle R(r,s)\leq {\binom {r+s-2}{r-1}}.}$ 

上述結果歸功於艾狄胥和塞凱賴什。當${\displaystyle r=s}$ 時，用史特靈公式化成：

${\displaystyle R(s,s)\leq [1+o(1)]{\frac {4^{s-1}}{\sqrt {\pi s}}},}$ 

其中誤差項o (1)，當${\displaystyle s}$ 趨向於無窮時，趨向${\displaystyle 0}$ 。

下界方面，1947年艾狄胥首創概率法（英语：Probabilistic method），證明

${\displaystyle R(s,s)\geq [1+o(1)]{\frac {s}{{\sqrt {2}}e}}2^{s/2}.}$ 

雖然上下界皆是指數形式，但兩者底數不同，實際大小相差甚遠，如${\displaystyle s=10}$ 時，給出的界是${\displaystyle 101\leq R(10,10)\leq 48620}$ 。不過，截至2021年，上下界的底數仍毫無改進，依舊是${\displaystyle 4}$ 和${\displaystyle {\sqrt {2}}}$ ，僅有較低階項的改進。而且，下界依賴非構造性的概率方法，未有任何確切構造^{[註 2]}能給出指數下界。暫時所知最佳結果為：

${\displaystyle [1+o(1)]{\frac {{\sqrt {2}}s}{e}}2^{\frac {s}{2}}\leq R(s,s)\leq s^{-(c\log s)/(\log \log s)}4^{s},}$ 

分別為斯賓塞（英语：Joel Spencer）和康倫（英语：David Conlon）所證。

至於非對角拉姆齊數${\displaystyle R(3,t)}$ ，已知其增長級別為${\displaystyle {\tfrac {t^{2}}{\log t}}}$ ；等價說法是，${\displaystyle n}$ 個頂點且無三角形（英语：triangle-free graph）的圖${\displaystyle G}$ ，獨立數${\displaystyle \alpha (G)}$ 的最小值用大Θ符號表示成

${\displaystyle \Theta \left({\sqrt {n\log n}}\right).}$ 

${\displaystyle R(3,t)}$ 的上界由奧伊陶伊（英语：Miklós Ajtai）、科姆洛什（英语：János Komlós (mathematician)）、塞迈雷迪證出，而${\displaystyle {\tfrac {t^{2}}{\log t}}}$ 級的下界原先由金正翰（英语：Jeong Han Kim）（音譯）證明，其後格里菲斯、莫里斯（英语：Robert Morris (mathematician)）、菲斯·庞蒂韦罗斯三人^[7]和波曼（英语：Tom Bohman）、基瓦什（英语：Peter Keevash）兩人^[8]藉分析「無三角形過程」，分別將下界獨立改進至

${\displaystyle \left({\frac {1}{4}}-o(1)\right){\frac {k^{2}}{\log k}}.}$ 

一般的非對角拉姆齊數${\displaystyle R(s,t)}$ ，當${\displaystyle s}$ 固定而${\displaystyle t}$ 增大時，已知最優的上下界為

${\displaystyle c'_{s}{\frac {t^{\frac {s+1}{2}}}{(\log t)^{{\frac {s+1}{2}}-{\frac {1}{s-2}}}}}\leq R(s,t)\leq c_{s}{\frac {t^{s-1}}{(\log t)^{s-2}}},}$ 

分別歸功於波曼、基瓦什兩人和奧伊陶伊、科姆洛什、塞迈雷迪三人。

延伸

無窮圖

参见：無窮元組合學

本定理可引伸適用於無窮圖，同樣稱為拉姆齊定理。與有限圖的拉姆齊定理相提並論時，或稱無窮拉姆齊定理（Infinite Ramsey theorem）以作區分。

設${\displaystyle X}$ 為無窮集，以${\displaystyle X^{(2)}}$ 表示其兩兩所連邊的集合（即${\displaystyle X}$ 全體二元子集組成的族），每邊染成${\displaystyle c}$ 色之一。則存在同色無窮階完全圖，即有無窮子集${\displaystyle M\subseteq X}$ ，其邊集${\displaystyle M^{(2)}}$ 同色。^[9][10]:1

證明：取任一${\displaystyle x_{1}\in X}$ 。自${\displaystyle x_{1}}$ 引出無窮多條邊，必有某色${\displaystyle c_{1}}$ 出現無窮多次。記${\displaystyle X_{1}\subseteq X\setminus \{x_{1}\}}$ 為該些邊另一端點的集合。又取任一${\displaystyle x_{2}\in X_{1}}$ ，同樣自${\displaystyle x_{2}}$ 有無窮多條邊引至${\displaystyle X_{1}\setminus \{x_{2}\}}$ ，故必有某色${\displaystyle c_{2}}$ 及無窮子集${\displaystyle X_{2}\subseteq X_{1}\setminus \{x_{2}\}}$ ，使${\displaystyle x_{2}}$ 引至${\displaystyle X_{2}}$ 的各邊皆染${\displaystyle c_{2}}$ 色。

餘可類推，得到一列互異的元素${\displaystyle x_{1},x_{2},\ldots \in X}$ 及一列顏色${\displaystyle c_{1},c_{2},\ldots }$ 。由於僅得有限多種色，必有顏色出現無窮多次，即有${\displaystyle c_{i_{1}}=c_{i_{2}}=\cdots }$ 對於無窮序列${\displaystyle i_{1}<i_{2}<\cdots }$ 成立。此時，有${\displaystyle M=\{x_{i_{1}},x_{i_{2}},x_{i_{3}},\ldots \}}$ 為無窮子集，且其元素兩兩連邊同色（因為邊${\displaystyle x_{i_{a}}x_{i_{b}}}$ 所染為${\displaystyle c_{i_{a}}}$ 色），證畢。

本定理對於超圖（即${\displaystyle X^{(2)}}$ 換成${\displaystyle X^{(r)}}$ ）亦成立。^[9][10]:2

關於無窮圖的二染色，艾狄胥－杜什尼克－米勒定理（英语：Erdős–Dushnik–Miller theorem）是較強的結果，但其中兩種顏色不對等。定理斷言，任意無窮圖（頂點數不必可數）的邊若染紅藍兩色，則或有可數無窮大的紅色完全子圖，或有與原圖同樣大的藍色完全子圖。^[11]

無窮推出有限

運用反證法，可以證明無窮拉姆齊定理推出有限拉姆齊定理。^[12]

反設有限拉姆齊定理不成立，即某個拉姆齊數不存在，則有整數${\displaystyle c}$ 和${\displaystyle T}$ 滿足：對任意正整數${\displaystyle k}$ ，完全圖${\displaystyle [k]^{(2)}}$ ^{[註 3]}皆有某種染${\displaystyle c}$ 色的方案，而不產生同色的${\displaystyle T}$ 元子集。以${\displaystyle C_{k}}$ 表示此種方案的集合。

對任意${\displaystyle k}$ ，可將${\displaystyle C_{k+1}}$ 中任意一種染色限制到子圖${\displaystyle [k]^{(2)}}$ （即刪去頂點${\displaystyle k+1}$ ），不會額外產生同色的${\displaystyle T}$ 元子集，所以所得的染色仍在${\displaystyle C_{k}}$ 中。${\displaystyle C_{k}}$ 中，某些染色是以上述方式，由${\displaystyle C_{k+1}}$ 的染色限制而成，此種染色構成${\displaystyle C_{k}}$ 的子集，記為${\displaystyle C_{k}^{1}}$ 。由假設，${\displaystyle C_{k+1}}$ 非空，所以${\displaystyle C_{k}^{1}}$ 亦非空。

同樣，${\displaystyle C_{k+1}^{1}}$ 元素的限制必屬${\displaystyle C_{k}^{1}}$ ，故可定義${\displaystyle C_{k}^{2}}$ 為此種限制所得染色法的集合，其不為空。類推對所有正整數${\displaystyle m,k}$ 定義${\displaystyle C_{k}^{m}}$ 。

現對每個正整數${\displaystyle k}$ ，有${\displaystyle C_{k}\supseteq C_{k}^{1}\supseteq C_{k}^{2}\supseteq \cdots }$ ，且逐個集合非空。又${\displaystyle C_{k}}$ 為有限集，因為由乘法原理，全體染色方案，不論是否有同色${\displaystyle T}$ 元集，總數是${\displaystyle c^{\binom {k}{2}}}$ 。由此，整個序列的交集${\displaystyle D_{k}=C_{k}\cap C_{k}^{1}\cap C_{k}^{2}\cap \cdots }$ 非空。^{[註 4]}又每個${\displaystyle C_{k}^{i}}$ 的元素來自${\displaystyle C_{k+1}^{i-1}}$ 某元素的限制，可知${\displaystyle D_{k}}$ 每個元素都來自${\displaystyle D_{k+1}}$ 元素的限制，從而由${\displaystyle D_{k}}$ 的染色出發，可以延拓成${\displaystyle D_{k+1}}$ 的染色，並可重複，直至得到無窮圖${\displaystyle \mathbb {N} ^{(2)}}$ 的染色，而無同色${\displaystyle T}$ 元集，與無窮拉姆齊定理矛盾。

以拓撲學觀之，此為標準的緊論證（compactness argument）^[12]，相當於考慮全體染色的拓撲空間${\displaystyle [c]^{\binom {\mathbb {N} }{2}}}$ ，而由吉洪諾夫定理，其為若干個有限（從而緊）空間${\displaystyle [c]}$ 之積，所以仍為緊。而條件「在子圖${\displaystyle [k]^{(2)}}$ 上不產生同色${\displaystyle T}$ 元集」，描述該空間的一個閉開集，所以有限交非空推出全體交非空。

超圖

定理亦可推廣至超图。一個${\displaystyle m}$ 均勻超圖（或${\displaystyle m}$ 超圖）就是將圖的邊由二元子集換成${\displaystyle m}$ 元子集。超圖拉姆齊定理敍述如下：

對任意正整數${\displaystyle m}$ 和${\displaystyle c}$ ，以及任意正整數${\displaystyle n_{1},n_{2},\ldots ,n_{c}}$ ，存在拉姆齊數${\displaystyle R(n_{1},\ldots ,n_{c};c,m)}$ ，使得${\displaystyle R(n_{1},\ldots ,n_{c};c,m)}$ 階完全${\displaystyle m}$ 超圖的各邊，不論如何染${\displaystyle c}$ 種色，必存在${\displaystyle i}$ 令圖中可找出某個衹染${\displaystyle i}$ 色的${\displaystyle n_{i}}$ 階完全${\displaystyle m}$ 超圖。

此定理一般對${\displaystyle m}$ 歸納證出，${\displaystyle m=2}$ 的初始情況正如前文。

有向圖

亦可定義有向圖的拉姆齊數，最早由P. Erdős and L. Moser （1964）提出。設${\displaystyle R(n)}$ 為最小的正整數${\displaystyle Q}$ ，使得${\displaystyle Q}$ 階完全圖中，若為每邊賦兩種定向之一（所得有向圖稱為循環賽圖（英语：tournament (graph theory)）），則必有無圈的${\displaystyle n}$ 階循環賽圖^{[註 5]} 。

此前${\displaystyle R(n,n;2)}$ 定義為保證${\displaystyle Z}$ 階完全無向圖染兩色會有同色完全${\displaystyle n}$ 階子圖的最小${\displaystyle Z}$ 值，可見${\displaystyle R(n)}$ 是${\displaystyle R(n,n;2)}$ 的有向類比：兩種顏色現換成邊的兩種方向，而「同色」換成「全部邊方向統一」（所以無圈）。

已知${\displaystyle R(0)=0}$ ，${\displaystyle R(1)=1}$ ，${\displaystyle R(2)=2}$ ，${\displaystyle R(3)=4}$ ，${\displaystyle R(4)=8}$ ，${\displaystyle R(5)=14}$ ，${\displaystyle R(6)=28}$ ，${\displaystyle 34\leq R(7)\leq 47}$ 。^[13][14]

註

1. 有些作者如（Brualdi 2010）及（Harary 1972）要求${\displaystyle k,l>1}$ ，以免對單一頂點（從而無邊）的圖的邊染色。亦有（Gross 2008）和（Erdős & Szekeres 1935）等作者將兩種色換成有邊與否，從而定理敍述變成：在足夠大的簡單圖中，必有${\displaystyle r}$ 團或${\displaystyle s}$ 獨立集。此形式下或可更自然地考慮單頂點的圖。
2. 意即多項式時間算法的輸出結果。
3. 為方便起見，頂點集設為${\displaystyle [k]=\{1,2,3,\ldots ,k\}}$ 。
4. 考慮元素個數的最小值為何。
5. 又稱遞移（transitive）循環賽圖。

參考文獻

1. Ramsey, F. P. On a Problem of Formal Logic [論形式邏輯的一個問題]. Proceedings of the London Mathematical Society. 1930, s2–30 (1): 264–286. doi:10.1112/plms/s2-30.1.264 （英语）. 
2. Gleason, A. M.; Greenwood, R. E.; Kelly, L. M. (编). The William Lowell Putnam Mathematical Competition Problems and Solutions: 1938–1964 [威廉·羅威爾·普特南數學競賽問題和解答：1938－1964]. Mathematical Association of America. 1980: 38. ISBN 9780883854624 （英语）. 
3. Liu, Andy; Leigh, Robert Barrington (编). Hungarian Problem Book IV: Based on the Eötvös Competitions 1947–1963 [匈牙利問題集四：選自厄特沃什比賽1947－1963]. 2011: 1. ISBN 9780883858318. doi:10.5948/UPO9781614444053 （英语）. 
4. Radziszowski, Stanisław. . The Electronic Journal of Combinatorics. 2021-01-15. 1994-08-01 [2021-12-29]. doi:10.37236/21. （原始内容存档于2022-04-07） （英语）. 
5. Brendan D. McKay, Stanislaw P. Radziszowski. R(4,5) = 25 (PDF). Journal of Graph Theory. May 1995, 19 (3): 309–322 [2019-01-05]. doi:10.1002/jgt.3190190304. （原始内容 (PDF)于2021-02-25）. 
6. Exoo, Geoffrey; Tatarevic, Milos. New Lower Bounds for 28 Classical Ramsey Numbers. The Electronic Journal of Combinatorics. 2015, 22 (3): 3 [2018-09-02]. （原始内容于2021-02-28）. 
7. Fiz Pontiveros, Gonzalo; Griffiths, Simon; Morris, Robert. The Triangle-Free Process and the Ramsey Number R(3, t) [無三角形過程與拉姆齊數R(3, t)]. Memoirs of the American Mathematical Society. 2020, 263 (1274) [2013]. arXiv:1302.6279  . doi:10.1090/memo/1274 （英语）. 
8. Bohman, Tom; Keevash, Peter. Dynamic concentration of the triangle-free process [無三角形過程的動力集中性]. The Seventh European Conference on Combinatorics, Graph Theory and Applications. CRM Series (Pisa: Edizioni della Normale). 2013, 16. arXiv:1302.5963  . doi:10.1007/978-88-7642-475-5_78 （英语）. 
9. Martin Gould. (PDF). [2021-12-20]. （原始内容 (PDF)存档于2021-11-26） （英语）. 
10. I. B. Leader (Lecture notes taken by P. A. Russell). (PDF). [2021-12-20]. （原始内容 (PDF)存档于2022-01-21） （英语）. 
11. Dushnik, Ben; Miller, E. W. Partially ordered sets [偏序集]. American Journal of Mathematics. 1941, 63 (3): 600–610. JSTOR 2371374. MR 0004862. doi:10.2307/2371374. hdl:10338.dmlcz/100377   （英语）.  尤其見定理5.22與5.23。
12. Diestel, Reinhard. Chapter 8, Infinite Graphs [第8章：無窮圖]. Graph Theory [圖論] 4. Heidelberg: Springer-Verlag. 2010: 209–2010. ISBN 978-3-662-53621-6 （英语）. 
13. Smith, Warren D.; Exoo, Geoff. . [2020-06-02]. （原始内容存档于2021-11-26） （英语）. 
14. Neiman, David; Mackey, John; Heule, Marijn. Tighter Bounds on Directed Ramsey Number R(7) [有向拉姆齊數R(7)較緊的界]. 2020-11-01. arXiv:2011.00683   [math.CO] （英语）. 

外部链接