拉姆齐定理 在组合数学上，拉姆齐定理（），又称拉姆齐二染色定理，断言对任意正整数formula_1和formula_2，若一个聚会的人数formula_3足够大，则无论相识关系如何，必定有formula_1个人相识或formula_2个人互不相识。给定formula_6时，保证前述结论的最小formula_3值称为拉姆齐数formula_8，其值取决于formula_6。用图论术语复述：若将足够大的完全图各边染红蓝两色，则不论如何染，必定有红色的formula_1阶完全图或蓝色的formula_2阶完全图。 拉姆齐定理是组合数学的重要结论，以弗兰克·普伦普顿·拉姆齐命名。他在1930年论文-{zh-cn:《;zh-my:《;zh-sg:《;zh-hk:《;zh-mo:《;zh-tw:〈;}-论形式逻辑的一个问题-{zh-cn:》;zh-my:》;zh-sg:》;zh-hk:》;zh-mo:》; zh-tw:〉;}-证明此定理最初的版本，开创现称拉姆齐理论的组合理论分支。拉姆齐理论的主题是从「无序」寻找「规律」，希望找出某数学结构中，存在规律子结构的一般条件。在拉姆齐定理的图论表述中，此「规律子结构」是同色集（-- ），即顶点集的子集，其中各边皆染成同一颜色。 拉姆齐定理不止一条，前述版本的若干引伸仍称拉姆齐定理。例如，可以将二染色推广至更多种色，此时定理断言：对任意色数formula_12，和任意正整数formula_13，必有某数formula_14，使formula_14阶的完全图各边不论如何染formula_12色，仍必可找到某formula_17（介于formula_18至formula_12）和某formula_20阶完全子图，其各边皆染第formula_17色。可见拉姆齐二染色定理是formula_22的特例（同时取formula_23）。 例. "R" (3, 3) = 6. 在6个顶点的完全图formula_24内，每边涂上红或蓝色。欲证必然有一个红色的三角形或蓝色的三角形。 以上论证对一切染色法都适用，所以formula_24的任何二染色皆有同色formula_32，换言之formula_33。这个定理的通俗版本称为朋友与陌路人定理。 另一种证法是算两次：考虑「异色角」的数目，即满足formula_34为红而formula_35为蓝的有序三顶点组formula_36的个数。若先固定中间的顶点formula_37，则对应三元组的数目可能是 所以，至多是formula_41，而formula_37本身有6种可能，异色角的总数至多是formula_43。但是，对于三边不完全同色的三角形，恰好有两只异色角，所以，至多有formula_44个异色三角形。考虑到6个顶点组成formula_45个三角形，至少有两个是同色三角形，再次得到formula_33的结论。 反之，将formula_47二染色，不一定有同色的三角形。此构造在同构意义下唯一，如下图所示：将五个顶点排成一圈，每个端点和毗邻的两个端点之间的连线染红色，与其余两个端点的连线染蓝色，则不产生同色三角形。所以，formula_48。 1953年普特南数学竞赛考过formula_49。1947年匈牙利屈尔沙克·约瑟夫数学比赛（）亦然。 "R" (3, 3, 3) = 17. 多色拉姆齐数就是用三种或更多颜色的拉姆齐数。若不考虑对称的情况，仅有两个非平凡的多色拉姆齐数为已知：formula_50和formula_51。 设将某完全图的边染红绿蓝三色，而无同色三角形。选任一顶点formula_52，考虑以红边与formula_52相连的各点，组成formula_52的「红邻域」。红邻域之内不能再有任何红边，否则该红边与formula_52一同组成红色三角形。所以红邻域内的边衹用蓝绿两色。由上节formula_48，formula_52的红邻域最多衹有5个顶点，否则有蓝或绿的同色三角形。同理，formula_52的绿邻域和蓝邻域，各有至多5个顶点，但图中每个顶点，或为formula_52本身，或属formula_52的某色邻域，所以全图至多formula_61个顶点。故formula_62。 欲证formula_63，现需用三种颜色画出16个顶点的完全图，而不产生同色三角形。若不辨同构之异，则恰有两种画法，分别称为「无扭」（-- ）和「有扭」（-- ）染法，见上图。 formula_64的有扭或无扭染色中，选任一颜色，该色边组成的子图都是。 对较少顶点的完全图，已知formula_65亦只得两种染三色的方法无同色三角形，分别来自formula_64的两种染法，删去任意一个顶点。formula_67则有115种方法染三色而无同色三角形，但此数不仅不辨图同构（顶点的置换），还不辨颜色的置换。 拉姆齐数. 定义. 拉姆齐数，用图论的语言有两种描述： 拉姆齐证明，对与给定的正整数数"k"及"l"，R("k","l")的答案是唯一和有限的。 拉姆齐数亦可推广到多于两个数： 对于完全图formula_68的每条边都任意涂上"r"种颜色之一，分别记为formula_74，在formula_68中，必定有个颜色为formula_76的formula_77阶子完全图，或有个颜色为formula_78的formula_79阶子完全图……或有个颜色为formula_80的formula_81阶子完全图。符合条件又最少的数"n"则记为formula_82。 数值或上下界. 已知的拉姆齐数非常少，保罗·艾狄胥曾以一个譬喻来描述寻找拉姆齐数的难度：「想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若他们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了。」#重定向 -{H|zh-hans:重定向;zh-hant:重新导向;}--{H|zh-cn:字符;zh-tw:字元;}--{H|zh-hans:文件; zh-hant:档案;}--{H|zh-hans:快捷方式; zh-hant:捷径;}--{H|zh-hans:项目;zh-hant:专案;zh-tw:计划;zh-hk:计划;zh-mo:计划;}--{H|zh-cn:计算机; zh-sg:电脑; zh-tw:电脑;}- 显然易见的公式： R(0,"s")=0， R(1,"s")=1， R(2,"s")="s"， formula_83（将formula_84的顺序改变并不改变拉姆齐的数值）。 有不定期更新的动态综述，介绍拉姆齐数的研究成果。 渐近性质. 拉姆齐数满足不等式formula_85。由此，利用数学归纳法，可以证明 formula_86 上述结果归功于艾狄胥和塞凯赖什。当formula_87时，用史特灵公式化成： formula_88 其中误差项"o" (1)，当formula_89趋向于无穷时，趋向formula_90。 下界方面，1947年艾狄胥首创，证明 formula_91 虽然上下界皆是指数形式，但两者底数不同，实际大小相差甚远，如formula_92时，给出的界是formula_93。不过，截至2021年，上下界的底数仍毫无改进，依旧是formula_94和formula_95，仅有较低阶项的改进。而且，下界依赖非构造性的概率方法，未有任何确切构造能给出指数下界。暂时所知最佳结果为： formula_96 分别为和所证。 至于非对角拉姆齐数formula_97，已知其增长级别为formula_98；等价说法是，formula_3个顶点且的图formula_100，独立数formula_101的最小值用大Θ符号表示成 formula_102 formula_97的上界由、、塞迈雷迪证出，而formula_98级的下界原先由（音译）证明，其后格里菲斯、、菲斯·庞蒂韦罗斯三人和、两人藉分析「无三角形过程」，分别将下界独立改进至 formula_105 一般的非对角拉姆齐数formula_106，当formula_89固定而formula_108增大时，已知最优的上下界为 formula_109 分别归功于波曼、基瓦什两人和奥伊陶伊、科姆洛什、塞迈雷迪三人。 延伸. 无穷图. 本定理可引伸适用于无穷图，同样称为拉姆齐定理。与有限图的拉姆齐定理相提并论时，或称无穷拉姆齐定理（-- ）以作区分。 设formula_110为无穷集，以formula_111表示其两两所连边的集合（即formula_110全体二元子集组成的族），每边染成formula_12色之一。则存在同色无穷阶完全图，即有无穷子集formula_114，其边集formula_115同色。:1 证明：取任一formula_116。自formula_117引出无穷多条边，必有某色formula_118出现无穷多次。记formula_119为该些边另一端点的集合。又取任一formula_120，同样自formula_121有无穷多条边引至formula_122，故必有某色formula_123及无穷子集formula_124，使formula_121引至formula_126的各边皆染formula_123色。 余可类推，得到一列互异的元素formula_128及一列颜色formula_129。由于仅得有限多种色，必有颜色出现无穷多次，即有formula_130对于无穷序列formula_131成立。此时，有formula_132为无穷子集，且其元素两两连边同色（因为边formula_133所染为formula_134色），证毕。 本定理对于超图（即formula_111换成formula_136）亦成立。:2 关于无穷图的二染色，是较强的结果，但其中两种颜色不对等。定理断言，任意无穷图（顶点数不必可数）的边若染红蓝两色，则或有可数无穷大的红色完全子图，或有与原图同样大的蓝色完全子图。 无穷推出有限. 运用反证法，可以证明无穷拉姆齐定理推出有限拉姆齐定理。 反设有限拉姆齐定理不成立，即某个拉姆齐数不存在，则有整数formula_12和formula_138满足：对任意正整数formula_1，完全图formula_140皆有某种染formula_12色的方案，而不产生同色的formula_138元子集。以formula_143表示此种方案的集合。 对任意formula_1，可将formula_145中任意一种染色限制到子图formula_140（即删去顶点formula_147），不会额外产生同色的formula_138元子集，所以所得的染色仍在formula_143中。formula_143中，某些染色是以上述方式，由formula_145的染色限制而成，此种染色构成formula_143的子集，记为formula_153。由假设，formula_145非空，所以formula_153亦非空。 同样，formula_156元素的限制必属formula_153，故可定义formula_158为此种限制所得染色法的集合，其不为空。类推对所有正整数formula_159定义formula_160。 现对每个正整数formula_1，有formula_162，且逐个集合非空。又formula_143为有限集，因为由乘法原理，全体染色方案，不论是否有同色formula_138元集，总数是formula_165。由此，整个序列的交集formula_166非空。又每个formula_167的元素来自formula_168某元素的限制，可知formula_169每个元素都来自formula_170元素的限制，从而由formula_169的染色出发，可以延拓成formula_170的染色，并可重复，直至得到无穷图formula_173的染色，而无同色formula_138元集，与无穷拉姆齐定理矛盾。 以拓扑学观之，此为标准的紧论证（-- ），相当于考虑全体染色的拓扑空间formula_175，而由吉洪诺夫定理，其为若干个有限（从而紧）空间formula_176之积，所以仍为紧。而条件「在子图formula_140上不产生同色formula_138元集」，描述该空间的一个闭开集，所以有限交非空推出全体交非空。 超图. 定理亦可推广至超图。一个formula_179均匀超图（或formula_179超图）就是将图的边由二元子集换成formula_179元子集。超图拉姆齐定理敍述如下： 对任意正整数formula_179和formula_12，以及任意正整数formula_13，存在拉姆齐数formula_185，使得formula_185阶完全formula_179超图的各边，不论如何染formula_12种色，必存在formula_17令图中可找出某个衹染formula_17色的formula_20阶完全formula_179超图。 此定理一般对formula_179归纳证出，formula_194的初始情况正如前文。 有向图. 亦可定义有向图的拉姆齐数，最早由P. Erdős and L. Moser （1964）提出。设formula_195为最小的正整数formula_196，使得formula_196阶完全图中，若为每边赋两种定向之一（所得有向图称为），则必有无圈的formula_3阶循环赛图 。 此前formula_199定义为保证formula_200阶完全无向图染两色会有同色完全formula_3阶子图的最小formula_200值，可见formula_195是formula_199的有向类比：两种颜色现换成边的两种方向，而「同色」换成「全部边方向统一」（所以无圈）。 已知formula_205，formula_206，formula_207，formula_208，formula_209，formula_210，formula_211，formula_212。