跳转到内容

拉姆齐定理

维基百科,自由的百科全书

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

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

拉姆齐定理不止一条,前述版本的若干引伸仍称拉姆齐定理。例如,可以将二染色推广至更多种色,此时定理断言:对任意色数,和任意正整数,必有某数,使阶的完全图各边不论如何染色,仍必可找到某(介于)和某阶完全子图,其各边皆染第色。可见拉姆齐二染色定理是的特例(同时取)。

R (3, 3) = 6

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

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

以上论证对一切染色法都适用,所以的任何二染色皆有同色,换言之。这个定理的通俗版本称为朋友与陌路人定理

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

  • (若其全部边染同色);
  • (若有四边染某色,另一边不同色);或
  • (若有三边染某色,另两边染另一色)。

所以,至多是,而本身有6种可能,异色角的总数至多是。但是,对于三边不完全同色的三角形,恰好有两只异色角,所以,至多有个异色三角形。考虑到6个顶点组成个三角形,至少有两个是同色三角形,再次得到的结论。

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

1953年普特南数学竞赛考过[2]1947年匈牙利屈尔沙克·约瑟夫数学比赛(匈牙利语Kürschák József Matematikai Tanulóverseny)亦然。[3]

R (3, 3, 3) = 17

多色拉姆齐数就是用三种或更多颜色的拉姆齐数。若不考虑对称的情况,仅有两个非平凡的多色拉姆齐数为已知:[4]

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

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

克莱布殊图英语Clebsch graph

的有扭或无扭染色中,选任一颜色,该色边组成的子图都是克莱布殊图英语Clebsch graph

对较少顶点的完全图,已知亦衹得两种染三色的方法无同色三角形,分别来自的两种染法,删去任意一个顶点。则有115种方法染三色而无同色三角形,但此数不仅不辨图同构(顶点的置换),还不辨颜色的置换。

拉姆齐数

定义

拉姆齐数,用图论的语言有两种描述:

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

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

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

对于完全图的每条边都任意涂上r种颜色之一,分别记为,在中,必定有个颜色为阶子完全图,或有个颜色为阶子完全图……或有个颜色为阶子完全图。符合条件又最少的数n则记为

数值或上下界

已知的拉姆齐数非常少,保罗·艾狄胥曾以一个譬喻来描述寻找拉姆齐数的难度:“想像有队外星人军队在地球降落,要求取得R(5,5)的值,否则便会毁灭地球。在这个情况,我们应该集中所有电脑和数学家尝试去找这个数值。若他们要求的是R(6,6)的值,我们要尝试毁灭这班外星人了。”[来源请求]

显然易见的公式: R(0,s)=0, R(1,s)=1, R(2,s)=s(将的顺序改变并不改变拉姆齐的数值)。

拉姆齐数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]

渐近性质

拉姆齐数满足不等式。由此,利用数学归纳法,可以证明

上述结果归功于艾狄胥塞凯赖什。当时,用史特灵公式化成:

其中误差项o (1),当趋向于无穷时,趋向

下界方面,1947年艾狄胥首创概率法英语Probabilistic method,证明

虽然上下界皆是指数形式,但两者底数不同,实际大小相差甚远,如时,给出的界是。不过,截至2021年,上下界的底数仍毫无改进,依旧是,仅有较低阶项的改进。而且,下界依赖非构造性的概率方法,未有任何确切构造[注 2]能给出指数下界。暂时所知最佳结果为:

分别为斯宾塞英语Joel Spencer康伦英语David Conlon所证。

至于非对角拉姆齐数,已知其增长级别为;等价说法是,个顶点且无三角形英语triangle-free graph的图独立数的最小值用大Θ符号表示成

的上界由奥伊陶伊英语Miklós Ajtai科姆洛什英语János Komlós (mathematician)塞迈雷迪证出,而级的下界原先由金正翰英语Jeong Han Kim(音译)证明,其后格里菲斯、莫里斯英语Robert Morris (mathematician)、菲斯·庞蒂韦罗斯三人[7]波曼英语Tom Bohman基瓦什英语Peter Keevash两人[8]藉分析“无三角形过程”,分别将下界独立改进至

一般的非对角拉姆齐数,当固定而增大时,已知最优的上下界为

分别归功于波曼、基瓦什两人和奥伊陶伊、科姆洛什、塞迈雷迪三人。

延伸

无穷图

本定理可引伸适用于无穷图,同样称为拉姆齐定理。与有限图的拉姆齐定理相提并论时,或称无穷拉姆齐定理(Infinite Ramsey theorem)以作区分。

为无穷集,以表示其两两所连边的集合(即全体二元子集组成的族),每边染成色之一。则存在同色无穷阶完全图,即有无穷子集,其边集同色。[9][10]:1

证明:取任一。自引出无穷多条边,必有某色出现无穷多次。记为该些边另一端点的集合。又取任一,同样自有无穷多条边引至,故必有某色及无穷子集,使引至的各边皆染色。

馀可类推,得到一列互异的元素及一列颜色。由于仅得有限多种色,必有颜色出现无穷多次,即有对于无穷序列成立。此时,有为无穷子集,且其元素两两连边同色(因为边所染为色),证毕。

本定理对于超图(即换成)亦成立。[9][10]:2

关于无穷图的二染色,艾狄胥-杜什尼克-米勒定理英语Erdős–Dushnik–Miller theorem是较强的结果,但其中两种颜色不对等。定理断言,任意无穷图(顶点数不必可数)的边若染红蓝两色,则或有可数无穷大的红色完全子图,或有与原图同样大的蓝色完全子图。[11]

无穷推出有限

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

反设有限拉姆齐定理不成立,即某个拉姆齐数不存在,则有整数满足:对任意正整数,完全图[注 3]皆有某种染色的方案,而不产生同色的元子集。以表示此种方案的集合。

对任意,可将中任意一种染色限制到子图(即删去顶点),不会额外产生同色的元子集,所以所得的染色仍在中。中,某些染色是以上述方式,由的染色限制而成,此种染色构成的子集,记为。由假设,非空,所以亦非空。

同样,元素的限制必属,故可定义为此种限制所得染色法的集合,其不为空。类推对所有正整数定义

现对每个正整数,有,且逐个集合非空。又为有限集,因为由乘法原理,全体染色方案,不论是否有同色元集,总数是。由此,整个序列的交集非空。[注 4]又每个的元素来自某元素的限制,可知每个元素都来自元素的限制,从而由的染色出发,可以延拓成的染色,并可重复,直至得到无穷图的染色,而无同色元集,与无穷拉姆齐定理矛盾。

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

超图

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

对任意正整数,以及任意正整数,存在拉姆齐数,使得阶完全超图的各边,不论如何染种色,必存在令图中可找出某个衹染色的阶完全超图。

此定理一般对归纳证出,的初始情况正如前文。

有向图

亦可定义有向图的拉姆齐数,最早由P. Erdős and L. Moser (1964提出。设为最小的正整数,使得阶完全图中,若为每边赋两种定向之一(所得有向图称为循环赛图英语tournament (graph theory)),则必有无圈的阶循环赛图[注 5]

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

已知[13][14]

注释

  1. ^ 有些作者如(Brualdi 2010)及(Harary 1972)要求,以免对单一顶点(从而无边)的图的边染色。亦有(Gross 2008)和(Erdős & Szekeres 1935)等作者将两种色换成有边与否,从而定理叙述变成:在足够大的简单图中,必有独立集。此形式下或可更自然地考虑单顶点的图。
  2. ^ 意即多项式时间算法的输出结果。
  3. ^ 为方便起见,顶点集设为
  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. ^ 4.0 4.1 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. ^ 6.0 6.1 6.2 6.3 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. ^ 9.0 9.1 Martin Gould. Ramsey Theory [拉姆齐理论] (PDF). [2021-12-20]. (原始内容 (PDF)存档于2021-11-26) (英语). 
  10. ^ 10.0 10.1 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. ^ 12.0 12.1 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] (英语). 

参考文献

外部链接