Loading AI tools
数学定理 来自维基百科,自由的百科全书
在组合数学上,拉姆齐定理(英语:Ramsey's theorem),又称拉姆齐二染色定理,断言对任意正整数和,若一个聚会的人数足够大,则无论相识关系如何,必定有个人相识或个人互不相识。给定时,保证前述结论的最小值称为拉姆齐数,其值取决于。用图论术语复述:若将足够大的完全图各边染红蓝两色,则不论如何染,必定有红色的阶完全图或蓝色的阶完全图。[注 1]
拉姆齐定理是组合数学的重要结论,以弗兰克·普伦普顿·拉姆齐命名。他在1930年论文《论形式逻辑的一个问题》[1]证明此定理最初的版本,开创现称拉姆齐理论的组合理论分支。拉姆齐理论的主题是从“无序”寻找“规律”,希望找出某数学结构中,存在规律子结构的一般条件。在拉姆齐定理的图论表述中,此“规律子结构”是同色集(monochromatic set),即顶点集的子集,其中各边皆染成同一颜色。
拉姆齐定理不止一条,前述版本的若干引伸仍称拉姆齐定理。例如,可以将二染色推广至更多种色,此时定理断言:对任意色数,和任意正整数,必有某数,使阶的完全图各边不论如何染色,仍必可找到某(介于至)和某阶完全子图,其各边皆染第色。可见拉姆齐二染色定理是的特例(同时取)。
在6个顶点的完全图内,每边涂上红或蓝色。欲证必然有一个红色的三角形或蓝色的三角形。
以上论证对一切染色法都适用,所以的任何二染色皆有同色,换言之。这个定理的通俗版本称为朋友与陌路人定理。
另一种证法是算两次:考虑“异色角”的数目,即满足为红而为蓝的有序三顶点组的个数。若先固定中间的顶点,则对应三元组的数目可能是
所以,至多是,而本身有6种可能,异色角的总数至多是。但是,对于三边不完全同色的三角形,恰好有两只异色角,所以,至多有个异色三角形。考虑到6个顶点组成个三角形,至少有两个是同色三角形,再次得到的结论。
反之,将二染色,不一定有同色的三角形。此构造在同构意义下唯一,如下图所示:将五个顶点排成一圈,每个端点和毗邻的两个端点之间的连线染红色,与其余两个端点的连线染蓝色,则不产生同色三角形。所以,。
1953年普特南数学竞赛考过。[2]1947年匈牙利屈尔沙克·约瑟夫数学比赛(匈牙利语:Kürschák József Matematikai Tanulóverseny)亦然。[3]
多色拉姆齐数就是用三种或更多颜色的拉姆齐数。若不考虑对称的情况,仅有两个非平凡的多色拉姆齐数为已知:和。[4]
设将某完全图的边染红绿蓝三色,而无同色三角形。选任一顶点,考虑以红边与相连的各点,组成的“红邻域”。红邻域之内不能再有任何红边,否则该红边与一同组成红色三角形。所以红邻域内的边只用蓝绿两色。由上节,的红邻域最多只有5个顶点,否则有蓝或绿的同色三角形。同理,的绿邻域和蓝邻域,各有至多5个顶点,但图中每个顶点,或为本身,或属的某色邻域,所以全图至多个顶点。故。
欲证,现需用三种颜色画出16个顶点的完全图,而不产生同色三角形。若不辨同构之异,则恰有两种画法,分别称为“无扭”(untwisted)和“有扭”(twisted)染法,见上图。
的有扭或无扭染色中,选任一颜色,该色边组成的子图都是克莱布殊图。
对较少顶点的完全图,已知亦只得两种染三色的方法无同色三角形,分别来自的两种染法,删去任意一个顶点。则有115种方法染三色而无同色三角形,但此数不仅不辨图同构(顶点的置换),还不辨颜色的置换。
拉姆齐数,用图论的语言有两种描述:
拉姆齐证明,对与给定的正整数数k及l,R(k,l)的答案是唯一和有限的。
拉姆齐数亦可推广到多于两个数:
已知的拉姆齐数非常少,保罗·艾狄胥曾以一个譬喻来描述寻找拉姆齐数的难度:“想像有队外星人军队在地球降落,要求取得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–46 | 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] 。
此前定义为保证阶完全无向图染两色会有同色完全阶子图的最小值,可见是的有向类比:两种颜色现换成边的两种方向,而“同色”换成“全部边方向统一”(所以无圈)。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.