拉姆齐定理

在组合数学上，拉姆齐定理（英语：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. Small Ramsey Numbers [小拉姆齐数]. 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. Ramsey Theory [拉姆齐理论] (PDF). [2021-12-20]. （原始内容 (PDF)存档于2021-11-26） （英语）.
10. I. B. Leader (Lecture notes taken by P. A. Russell). Ramsey Theory [拉姆齐理论] (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. Partial Answer to Puzzle #27: A Ramsey-like quantity [谜题27的部分解：某拉姆齐类数]. [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] （英语）.

参考文献

• Ajtai, Miklós; Komlós, János; Szemerédi, Endre, A note on Ramsey numbers, J. Combin. Theory Ser. A, 1980, 29 (3): 354–360, doi:10.1016/0097-3165(80)90030-8 .
• Bohman, Tom; Keevash, Peter, The early evolution of the H-free process, Invent. Math., 2010, 181 (2): 291–336, Bibcode:2010InMat.181..291B, S2CID 2429894, arXiv:0908.0429 , doi:10.1007/s00222-010-0247-x
• Brualdi, Richard A., Introductory Combinatorics 5th, Prentice-Hall: 77–82, 2010, ISBN 978-0-13-602040-0
• Conlon, David, A new upper bound for diagonal Ramsey numbers, Annals of Mathematics, 2009, 170 (2): 941–960, MR 2552114, S2CID 9238219, arXiv:math/0607788v1 , doi:10.4007/annals.2009.170.941.
• Erdős, Paul, Some remarks on the theory of graphs, Bull. Amer. Math. Soc., 1947, 53 (4): 292–294, doi:10.1090/S0002-9904-1947-08785-1 .
• Erdős, P.; Moser, L., On the representation of directed graphs as unions of orderings (PDF), A Magyar Tudományos Akadémia, Matematikai Kutató Intézetének Közleményei, 1964, 9: 125–132 [2023-11-06], MR 0168494, （原始内容存档 (PDF)于2022-12-23）
• Erdős, Paul; Szekeres, George, A combinatorial problem in geometry (PDF), Compositio Mathematica, 1935, 2: 463–470 [2023-11-06], ISBN 978-0-8176-4841-1, doi:10.1007/978-0-8176-4842-8_3, （原始内容存档 (PDF)于2023-11-06）.
• Exoo, G., A lower bound for R(5,5), Journal of Graph Theory, 1989, 13: 97–98, doi:10.1002/jgt.3190130113.
• Graham, R.; Rothschild, B.; Spencer, J. H., Ramsey Theory, New York: John Wiley and Sons, 1990.
• Gross, Jonathan L., Combinatorial Methods with Computer Applications, CRC Press: 458, 2008, ISBN 978-1-58488-743-0
• Harary, Frank, Graph Theory, Addison-Wesley: 16–17, 1972, ISBN 0-201-02787-9
• Ramsey, F. P., On a problem of formal logic, Proceedings of the London Mathematical Society, 1930, 30: 264–286, doi:10.1112/plms/s2-30.1.264.
• Spencer, J., Ramsey's theorem – a new lower bound, J. Combin. Theory Ser. A, 1975, 18: 108–115, doi:10.1016/0097-3165(75)90071-0 .
• Bian, Zhengbing; Chudak, Fabian; Macready, William G.; Clark, Lane; Gaitan, Frank, Experimental determination of Ramsey numbers, Physical Review Letters, 2013, 111 (13): 130505, Bibcode:2013PhRvL.111m0505B, PMID 24116761, S2CID 1303361, arXiv:1201.1842 , doi:10.1103/PhysRevLett.111.130505.

外部链接

• 证明R(3,6) = 18