拉姆齐定理
在组合数学上,拉姆齐定理(英语: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)染法,见上图。
的有扭或无扭染色中,选任一颜色,该色边组成的子图都是克莱布殊图。
对较少顶点的完全图,已知 亦只得两种染三色的方法无同色三角形,分别来自 的两种染法,删去任意一个顶点。 则有115种方法染三色而无同色三角形,但此数不仅不辨图同构(顶点的置换),还不辨颜色的置换。
拉姆齐数
定义
拉姆齐数,用图论的语言有两种描述:
- 对于所有的N顶图,包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数,记作R(k,l);
- 在着色理论中是这样描述的:对于完全图 的任意一个2边着色 ,使得 中含有一个k阶子完全图, 含有一个l阶子完全图,则称满足这个条件的最小的n为一个拉姆齐数。(注意: 按照图论的记法表示i阶完全图)
拉姆齐证明,对与给定的正整数数k及l,R(k,l)的答案是唯一和有限的。
拉姆齐数亦可推广到多于两个数:
- 对于完全图 的每条边都任意涂上r种颜色之一,分别记为 ,在 中,必定有个颜色为 的 阶子完全图,或有个颜色为 的 阶子完全图……或有个颜色为 的 阶子完全图。符合条件又最少的数n则记为 。
数值或上下界
已知的拉姆齐数非常少,保罗·艾狄胥曾以一个譬喻来描述寻找拉姆齐数的难度:“想像有队外星人军队在地球降落,要求取得R(5,5)的值,否则便会毁灭地球。在这个情况,我们应该集中所有电脑和数学家尝试去找这个数值。若他们要求的是R(6,6)的值,我们要尝试毁灭这班外星人了。”[来源请求]
显然易见的公式: R(0,s)=0, R(1,s)=1, R(2,s)=s, (将 的顺序改变并不改变拉姆齐的数值)。
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 |
组合电子期刊有不定期更新的动态综述,介绍拉姆齐数的研究成果。[4]
渐近性质
拉姆齐数满足不等式 。由此,利用数学归纳法,可以证明
其中误差项o (1),当 趋向于无穷时,趋向 。
下界方面,1947年艾狄胥首创概率法,证明
虽然上下界皆是指数形式,但两者底数不同,实际大小相差甚远,如 时,给出的界是 。不过,截至2021年,上下界的底数仍毫无改进,依旧是 和 ,仅有较低阶项的改进。而且,下界依赖非构造性的概率方法,未有任何确切构造[注 2]能给出指数下界。暂时所知最佳结果为:
至于非对角拉姆齐数 ,已知其增长级别为 ;等价说法是, 个顶点且无三角形的图 ,独立数 的最小值用大Θ符号表示成
的上界由奥伊陶伊、科姆洛什、塞迈雷迪证出,而 级的下界原先由金正翰(音译)证明,其后格里菲斯、莫里斯、菲斯·庞蒂韦罗斯三人[7]和波曼、基瓦什两人[8]藉分析“无三角形过程”,分别将下界独立改进至
一般的非对角拉姆齐数 ,当 固定而 增大时,已知最优的上下界为
分别归功于波曼、基瓦什两人和奥伊陶伊、科姆洛什、塞迈雷迪三人。
延伸
无穷图
本定理可引伸适用于无穷图,同样称为拉姆齐定理。与有限图的拉姆齐定理相提并论时,或称无穷拉姆齐定理(Infinite Ramsey theorem)以作区分。
设 为无穷集,以 表示其两两所连边的集合(即 全体二元子集组成的族),每边染成 色之一。则存在同色无穷阶完全图,即有无穷子集 ,其边集 同色。[9][10]:1
证明:取任一 。自 引出无穷多条边,必有某色 出现无穷多次。记 为该些边另一端点的集合。又取任一 ,同样自 有无穷多条边引至 ,故必有某色 及无穷子集 ,使 引至 的各边皆染 色。
余可类推,得到一列互异的元素 及一列颜色 。由于仅得有限多种色,必有颜色出现无穷多次,即有 对于无穷序列 成立。此时,有 为无穷子集,且其元素两两连边同色(因为边 所染为 色),证毕。
关于无穷图的二染色,艾狄胥-杜什尼克-米勒定理是较强的结果,但其中两种颜色不对等。定理断言,任意无穷图(顶点数不必可数)的边若染红蓝两色,则或有可数无穷大的红色完全子图,或有与原图同样大的蓝色完全子图。[11]
无穷推出有限
运用反证法,可以证明无穷拉姆齐定理推出有限拉姆齐定理。[12]
反设有限拉姆齐定理不成立,即某个拉姆齐数不存在,则有整数 和 满足:对任意正整数 ,完全图 [注 3]皆有某种染 色的方案,而不产生同色的 元子集。以 表示此种方案的集合。
对任意 ,可将 中任意一种染色限制到子图 (即删去顶点 ),不会额外产生同色的 元子集,所以所得的染色仍在 中。 中,某些染色是以上述方式,由 的染色限制而成,此种染色构成 的子集,记为 。由假设, 非空,所以 亦非空。
同样, 元素的限制必属 ,故可定义 为此种限制所得染色法的集合,其不为空。类推对所有正整数 定义 。
现对每个正整数 ,有 ,且逐个集合非空。又 为有限集,因为由乘法原理,全体染色方案,不论是否有同色 元集,总数是 。由此,整个序列的交集 非空。[注 4]又每个 的元素来自 某元素的限制,可知 每个元素都来自 元素的限制,从而由 的染色出发,可以延拓成 的染色,并可重复,直至得到无穷图 的染色,而无同色 元集,与无穷拉姆齐定理矛盾。
以拓扑学观之,此为标准的紧论证(compactness argument)[12],相当于考虑全体染色的拓扑空间 ,而由吉洪诺夫定理,其为若干个有限(从而紧)空间 之积,所以仍为紧。而条件“在子图 上不产生同色 元集”,描述该空间的一个闭开集,所以有限交非空推出全体交非空。
超图
定理亦可推广至超图。一个 均匀超图(或 超图)就是将图的边由二元子集换成 元子集。超图拉姆齐定理叙述如下:
对任意正整数 和 ,以及任意正整数 ,存在拉姆齐数 ,使得 阶完全 超图的各边,不论如何染 种色,必存在 令图中可找出某个只染 色的 阶完全 超图。
此定理一般对 归纳证出, 的初始情况正如前文。
有向图
亦可定义有向图的拉姆齐数,最早由P. Erdős and L. Moser (1964)提出。设 为最小的正整数 ,使得 阶完全图中,若为每边赋两种定向之一(所得有向图称为循环赛图),则必有无圈的 阶循环赛图[注 5] 。
此前 定义为保证 阶完全无向图染两色会有同色完全 阶子图的最小 值,可见 是 的有向类比:两种颜色现换成边的两种方向,而“同色”换成“全部边方向统一”(所以无圈)。
注释
- ^ 有些作者如(Brualdi 2010)及(Harary 1972)要求 ,以免对单一顶点(从而无边)的图的边染色。亦有(Gross 2008)和(Erdős & Szekeres 1935)等作者将两种色换成有边与否,从而定理叙述变成:在足够大的简单图中,必有 团或 独立集。此形式下或可更自然地考虑单顶点的图。
- ^ 意即多项式时间算法的输出结果。
- ^ 为方便起见,顶点集设为 。
- ^ 考虑元素个数的最小值为何。
- ^ 又称递移(transitive)循环赛图。
参考资料
- ^ 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 (英语).
- ^ 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 (英语).
- ^ 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.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) (英语).
- ^ 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.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).
- ^ 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 (英语).
- ^ 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.0 9.1 Martin Gould. Ramsey Theory [拉姆齐理论] (PDF). [2021-12-20]. (原始内容 (PDF)存档于2021-11-26) (英语).
- ^ 10.0 10.1 I. B. Leader (Lecture notes taken by P. A. Russell). Ramsey Theory [拉姆齐理论] (PDF). [2021-12-20]. (原始内容 (PDF)存档于2022-01-21) (英语).
- ^ 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.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 (英语).
- ^ Smith, Warren D.; Exoo, Geoff. Partial Answer to Puzzle #27: A Ramsey-like quantity [谜题27的部分解:某拉姆齐类数]. [2020-06-02]. (原始内容存档于2021-11-26) (英语).
- ^ 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.