拉姆齐定理

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）染法，见上图。

${\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}}$ 的顺序改变并不改变拉姆齐的数值）。

组合电子期刊（英语：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}$ ，解析失败 (SVG（MathML可通过浏览器插件启用）：从服务器“/mathoid/local/v1/”返回无效的响应（“Math extension cannot connect to Restbase.”）：): {\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]

• 证明R(3,6) = 18