拉姆齐定理

在组合数学上，拉姆齐定理（Ramsey's theorem），又称拉姆齐二染色定理，断言对任意正整数$k$和$l$，若一个聚会的人数$n$足够大，则无论相识关系如何，必定有$k$个人相识或$l$个人互不相识。给定$k, l$时，保证前述结论的最小$n$值称为拉姆齐数$R(k,l)$，其值取决于$k, l$。用图论术语复述：若将足够大的完全图各边染红蓝两色，则不论如何染，必定有红色的$k$阶完全图或蓝色的$l$阶完全图。有些作者如Brualdi及Harary要求$k, l > 1$，以免对单一顶点（从而无边）的图的边染色。亦有Gross和Erdős等作者将两种色换成有边与否，从而定理叙述变成：在足够大的简单图中，必有$r$团或$s$独立集。此形式下或可更自然地考虑单顶点的图。

拉姆齐定理是组合数学的重要结论，以弗兰克·普伦普顿·拉姆齐命名。他在1930年论文论形式逻辑的一个问题证明此定理最初的版本，开创现称拉姆齐理论的组合理论分支。拉姆齐理论的主题是从“无序”寻找“规律”，希望找出某数学结构中，存在规律子结构的一般条件。在拉姆齐定理的图论表述中，此“规律子结构”是同色集（monochromatic set），即顶点集的子集，其中各边皆染成同一颜色。

拉姆齐定理不止一条，前述版本的若干引伸仍称拉姆齐定理。例如，可以将二染色推广至更多种色，此时定理断言：对任意色数$c$，和任意正整数$n_1, n_2, \ldots, n_c$，必有某数$R(n_1, \ldots, n_c)$，使$R(n_1, \ldots, n_c)$阶的完全图各边不论如何染$c$色，仍必可找到某$i$（介于$1$至$c$）和某$n_i$阶完全子图，其各边皆染第$i$色。可见拉姆齐二染色定理是$c = 2$的特例（同时取$n_1 = k, n_2 = l$）。

## 例

### R (3, 3) = 6

<image>

在6个顶点的完全图$K_6$内，每边涂上红或蓝色。欲证必然有一个红色的三角形或蓝色的三角形。

- 任意选取一个端点$P$，它有5条边和其他端点相连。
- 根据鸽巢原理，5条边染两种颜色，至少有3边颜色相同，不失一般性设这种颜色是红色，又设该三边为$PA, PB, PC$。
- $A, B, C$三个顶点，互相连结的边有$AB, BC, CA$三条。
- 若这3条边中任何一条是红色，这条边的两个端点和$P$便组成一个红色三角形。
- 若这3条边中没有红边，则都是蓝色，因此，$ABC$是蓝色三角形。

以上论证对一切染色法都适用，所以$K_6$的任何二染色皆有同色$K_3$，换言之$R(3, 3)\le 6$。这个定理的通俗版本称为朋友与陌路人定理。

另一种证法是算两次：考虑“异色角”的数目，即满足$xy$为红而$yz$为蓝的有序三顶点组$(x, y, z)$的个数。若先固定中间的顶点$y$，则对应三元组的数目可能是

- $0 \times 5 = 0$（若其全部边染同色）。
- $1 \times 4 = 4$（若有四边染某色，另一边不同色）；或
- $2\times 3 = 6$（若有三边染某色，另两边染另一色）。

所以，至多是$6$，而$y$本身有6种可能，异色角的总数至多是$6 \times 6 = 36$。但是，对于三边不完全同色的三角形，恰好有两只异色角，所以，至多有$18$个异色三角形。考虑到6个顶点组成$\binom{6}{3} = 20$个三角形，至少有两个是同色三角形，再次得到$R(3, 3)\le 6$的结论。

反之，将$K_5$二染色，不一定有同色的三角形。此构造在同构意义下唯一，如下图所示：将五个顶点排成一圈，每个端点和毗邻的两个端点之间的连线染红色，与其余两个端点的连线染蓝色，则不产生同色三角形。所以，$R(3, 3) = 6$。

<image>

1953年普特南数学竞赛考过$R(3, 3) \le 6$。1947年匈牙利屈尔沙克·约瑟夫数学比赛（Kürschák József Matematikai Tanulóverseny）亦然。

### R (3, 3, 3) = 17

<image>

- 无扭的

<image>

- 有扭的

多色拉姆齐数就是用三种或更多颜色的拉姆齐数。若不考虑对称的情况，仅有两个非平凡的多色拉姆齐数为已知：$R(3, 3, 3) = 17$和$R(3, 3, 4) = 30$。

设将某完全图的边染红绿蓝三色，而无同色三角形。选任一顶点$v$，考虑以红边与$v$相连的各点，组成$v$的“红邻域”。红邻域之内不能再有任何红边，否则该红边与$v$一同组成红色三角形。所以红邻域内的边只用蓝绿两色。由上节$R(3, 3) = 6$，$v$的红邻域最多只有5个顶点，否则有蓝或绿的同色三角形。同理，$v$的绿邻域和蓝邻域，各有至多5个顶点，但图中每个顶点，或为$v$本身，或属$v$的某色邻域，所以全图至多$1+5+5+5 = 16$个顶点。故$R(3, 3, 3) \le 17$。

欲证$R( 3, 3, 3) = 17$，现需用三种颜色画出16个顶点的完全图，而不产生同色三角形。若不辨同构之异，则恰有两种画法，分别称为“无扭”（untwisted）和“有扭”（twisted）染法，见上图。

<image>

$K_{16}$的有扭或无扭染色中，选任一颜色，该色边组成的子图都是克莱布什图。

对较少顶点的完全图，已知$K_{15}$亦只得两种染三色的方法无同色三角形，分别来自$K_{16}$的两种染法，删去任意一个顶点。$K_{14}$则有115种方法染三色而无同色三角形，但此数不仅不辨图同构（顶点的置换），还不辨颜色的置换。

## 拉姆齐数

### 定义

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

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

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

拉姆齐数亦可推广到多于两个数：

对于完全图$K_n$的每条边都任意涂上r种颜色之一，分别记为$e_1,e_2,e_3, ... , e_r$，在$K_n$中，必定有个颜色为$e_1$的$l_1$阶子完全图，或有个颜色为$e_2$的$l_2$阶子完全图……或有个颜色为$e_r$的$l_r$阶子完全图。符合条件又最少的数n则记为$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。

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

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–41

$R(3,10) \leq 41$

4｜18｜25｜36–41｜49–61｜59–84｜73–115｜92–149

5｜43–46｜58–87｜80–143｜101–216｜133–316｜149–442

6｜102–165｜115–298｜134–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

组合电子期刊有不定期更新的动态综述，介绍拉姆齐数的研究成果。

### 渐近性质

拉姆齐数满足不等式$R(r, s) \le R(r - 1, s) + R(r, s - 1)$。由此，利用数学归纳法，可以证明

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

上述结果归功于艾狄胥和塞凯赖什。当$r = s$时，用史特灵公式化成：

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

其中误差项o (1)，当$s$趋向于无穷时，趋向$0$。

下界方面，1947年艾狄胥首创概率法，证明

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

虽然上下界皆是指数形式，但两者底数不同，实际大小相差甚远，如$s = 10$时，给出的界是$101 \le R(10, 10) \le 48620$。不过，截至2021年，上下界的底数仍毫无改进，依旧是$4$和$\sqrt 2$，仅有较低阶项的改进。而且，下界依赖非构造性的概率方法，未有任何确切构造意即多项式时间算法的输出结果。能给出指数下界。暂时所知最佳结果为：

$$[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,$$

分别为乔尔·斯宾塞和大卫·康伦所证。

至于非对角拉姆齐数$R(3, t)$，已知其增长级别为$\tfrac{t^2}{\log t}$；等价说法是，$n$个顶点且无三角形图的图$G$，独立数$\alpha(G)$的最小值用大Θ符号表示成

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

$R(3, t)$的上界由奥伊陶伊·米克洛什、科姆洛什·亚诺什、塞迈雷迪证出，而$\tfrac{t^2}{\log t}$级的下界原先由金正翰（音译）证明，其后格里菲斯、罗伯特·莫里斯 (数学家)、菲斯·庞蒂韦罗斯三人和汤姆·波曼、彼得·基瓦什两人藉分析“无三角形过程”，分别将下界独立改进至

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

一般的非对角拉姆齐数$R(s, t)$，当$s$固定而$t$增大时，已知最优的上下界为

$$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）以作区分。

设$X$为无穷集，以$X^{(2)}$表示其两两所连边的集合（即$X$全体二元子集组成的族），每边染成$c$色之一。则存在同色无穷阶完全图，即有无穷子集$M\subseteq X$，其边集$M^{(2)}$同色。

证明：取任一$x_1 \in X$。自$x_1$引出无穷多条边，必有某色$c_1$出现无穷多次。记$X_1 \subseteq X \setminus \{x_1\}$为该些边另一端点的集合。又取任一$x_2\in X_1$，同样自$x_2$有无穷多条边引至$X_1 \setminus \{x_2\}$，故必有某色$c_2$及无穷子集$X_2 \subseteq X_1 \setminus \{x_2\}$，使$x_2$引至$X_2$的各边皆染$c_2$色。

余可类推，得到一列互异的元素$x_1, x_2, \ldots \in X$及一列颜色$c_1, c_2, \ldots$。由于仅得有限多种色，必有颜色出现无穷多次，即有$c_{i_1} = c_{i_2} = \cdots$对于无穷序列$i_1 < i_2 < \cdots$成立。此时，有$M = \{ x_{i_1}, x_{i_2}, x_{i_3}, \ldots \}$为无穷子集，且其元素两两连边同色（因为边$x_{i_a}x_{i_b}$所染为$c_{i_a}$色），证毕。

本定理对于超图（即$X^{(2)}$换成$X^{(r)}$）亦成立。

关于无穷图的二染色，艾狄胥－杜什尼克－米勒定理是较强的结果，但其中两种颜色不对等。定理断言，任意无穷图（顶点数不必可数）的边若染红蓝两色，则或有可数无穷大的红色完全子图，或有与原图同样大的蓝色完全子图。

#### 无穷推出有限

运用反证法，可以证明无穷拉姆齐定理推出有限拉姆齐定理。

反设有限拉姆齐定理不成立，即某个拉姆齐数不存在，则有整数$c$和$T$满足：对任意正整数$k$，完全图$[k]^{(2)}$为方便起见，顶点集设为$[k] = \{1, 2, 3, \ldots, k\}$。皆有某种染$c$色的方案，而不产生同色的$T$元子集。以$C_k$表示此种方案的集合。

对任意$k$，可将$C_{k+1}$中任意一种染色限制到子图$[k]^{(2)}$（即删去顶点$k+1$），不会额外产生同色的$T$元子集，所以所得的染色仍在$C_k$中。$C_k$中，某些染色是以上述方式，由$C_{k+1}$的染色限制而成，此种染色构成$C_k$的子集，记为$C^1_k$。由假设，$C_{k+1}$非空，所以$C^1_k$亦非空。

同样，$C^1_{k+1}$元素的限制必属$C^1_k$，故可定义$C^2_k$为此种限制所得染色法的集合，其不为空。类推对所有正整数$m, k$定义$C^m_k$。

现对每个正整数$k$，有$C_k\supseteq C^1_k\supseteq C^2_k\supseteq \cdots$，且逐个集合非空。又$C_k$为有限集，因为由乘法原理，全体染色方案，不论是否有同色$T$元集，总数是$c^{\binom{k}{2}}$。由此，整个序列的交集$D_k=C_k\cap C^1_k\cap C^2_k\cap \cdots$非空。考虑元素个数的最小值为何。又每个$C_k^i$的元素来自$C_{k+1}^{i-1}$某元素的限制，可知$D_k$每个元素都来自$D_{k+1}$元素的限制，从而由$D_k$的染色出发，可以延拓成$D_{k+1}$的染色，并可重复，直至得到无穷图$\N^{(2)}$的染色，而无同色$T$元集，与无穷拉姆齐定理矛盾。

以拓扑学观之，此为标准的紧论证（compactness argument），相当于考虑全体染色的拓扑空间$[c]^{\binom{\N}{2}}$，而由吉洪诺夫定理，其为若干个有限（从而紧）空间$[c]$之积，所以仍为紧。而条件“在子图$[k]^{(2)}$上不产生同色$T$元集”，描述该空间的一个闭开集，所以有限交非空推出全体交非空。

### 超图

定理亦可推广至超图。一个$m$均匀超图（或$m$超图）就是将图的边由二元子集换成$m$元子集。超图拉姆齐定理叙述如下：

对任意正整数$m$和$c$，以及任意正整数$n_1, n_2, \ldots, n_c$，存在拉姆齐数$R(n_1, \ldots, n_c; c, m)$，使得$R(n_1, \ldots, n_c; c, m)$阶完全$m$超图的各边，不论如何染$c$种色，必存在$i$令图中可找出某个只染$i$色的$n_i$阶完全$m$超图。

此定理一般对$m$归纳证出，$m = 2$的初始情况正如前文。

### 有向图

亦可定义有向图的拉姆齐数，最早由提出。设$R(n)$为最小的正整数$Q$，使得$Q$阶完全图中，若为每边赋两种定向之一（所得有向图称为循环赛图），则必有无圈的$n$阶循环赛图又称递移（transitive）循环赛图。

此前$R(n, n; 2)$定义为保证$Z$阶完全无向图染两色会有同色完全$n$阶子图的最小$Z$值，可见$R(n)$是$R(n, n; 2)$的有向类比：两种颜色现换成边的两种方向，而“同色”换成“全部边方向统一”（所以无圈）。

已知$R(0) = 0$，$R(1) = 1$，$R(2) = 2$，$R(3) = 4$，$R(4) = 8$，$R(5) = 14$，$R(6) = 28$，$34 \le R(7) \le 47$。