拉姆齐定理

在组合数学上，拉姆齐定理（英语：Ramsey's theorem），又称拉姆齐二染色定理，断言对任意正整数$k$和$l$，若一个聚会的人数$n$足够大，则无论相识关系如何，必定有$k$个人相识或$l$个人互不相识。给定$k,l$时，保证前述结论的最小$n$值称为拉姆齐数$R(k,l)$，其值取决于$k,l$。用图论术语复述：若将足够大的完全图各边染红蓝两色，则不论如何染，必定有红色的$k$阶完全图或蓝色的$l$阶完全图。

拉姆齐定理是组合数学的重要结论，以弗兰克·普伦普顿·拉姆齐命名。他在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

在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)\leq 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)\leq 6$的结论。

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

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

R (3, 3, 3) = 17

• 仅有两种方法将16个顶点之间的边染三种颜色而无同色三角形
• 
  无扭的
• 
  有扭的

多色拉姆齐数就是用三种或更多颜色的拉姆齐数。若不考虑对称的情况，仅有两个非平凡的多色拉姆齐数为已知：$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)\leq 17$。

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

克莱布殊图

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

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

拉姆齐数

定义

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

1. 对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；
2. 在着色理论中是这样描述的：对于完全图$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(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	36–41	49–61	59–84	73–115	92–149
5					43–48	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)\leq 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\leq R(10,10)\leq 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)}$皆有某种染$c$色的方案，而不产生同色的$T$元子集。以$C_{k}$表示此种方案的集合。

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

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

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

以拓扑学观之，此为标准的紧论证（compactness argument），相当于考虑全体染色的拓扑空间$[c]^{\binom {\mathbb {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$的初始情况正如前文。

有向图

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

此前$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\leq R(7)\leq 47$。

参考文献

• 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