拉姆齐定理

数学术语

拉姆齐理论是以英国数学家和哲学家弗兰克·P·拉姆齐（Frank P. Ramsey）的名字命名的，是数学的一个分支，致力于研究必须出现阶数的条件。拉姆齐理论中的问题通常会问一个形式的问题：“某种结构中必须有多少个元素才能保证特定的性质能够持有”。

定理定义

在组合数学上，拉姆齐(Ramsey)定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。

通俗表述

6 个人中至少存在3人相互认识或者相互不认识。

该定理等价于证明这6个顶点的完全图的边，用红、蓝二色任意着色，必然至少存在一个红色边三角形，或蓝色边三角形。

例子

拉姆齐理论的一个典型结果是从一些数学结构开始，然后将其切成碎片。为了确保至少其中一部分具有给定的有趣属性，原始结构必须达到多大，这个想法可以定义为分区规则。

例如，考虑一个n阶的完整图。也就是说，有n个顶点，并且每个顶点通过一条边连接到其他每个顶点。 3阶的完整图称为三角形。然后将每条边缘都涂成红色或蓝色。为了确保有蓝色三角形或红色三角形，事实证明n必须是6。

表达此结果的另一种方法如下：在至少有六个人的任何一方中，有三个人都是互相认识的（每个人都认识另外两个）或互相陌生的（每个人都不知道另两个人）。

这也是拉姆西定理的特例，该定理说，对于任何给定的整数c，任何给定的整数n1，...，nc，都有一个数字R（n1，...，nc），使得如果R（n1，...，nc）阶的完整图的边用c种不同的颜色着色，那么对于介于1和c之间的某些i，它必须包含一个ni阶的完整子图，其边都是i。上面的特殊情况有c = 2和n1 = n2 = 3。

验证推导

R(3,3)=6

证明如下：首先，把这6个人设为A、B、C、D、E、F六个点。由A点可以引出AB、AC、AD、AE、AF五条线段。设：如果两个人认识，则设这两个人组成的线段为红色；如果两个人不认识，则设这两个人组成的线段为蓝色。

由抽屉原理可知：这五条线段中至少有三条是同色的。不妨设AB、AC、AD为红色。若BC或CD为红色，则结论显然成立。若BC和CD均为蓝色，则若BD为红色，则一定有三个人相互认识；若BD为蓝色，则一定有三个人互相不认识。

关键定理

Van der Waerden定理

对于任何给定的c和n，都有一个数字V，因此，如果V个连续数字用c种不同的颜色着色，则它必须包含长度为n的算术级数，其元素都是相同的颜色。

Hales–Jewett定理

对于任何给定的n和c，都有一个数字H，如果H维n×n×n×...×n立方体的像元用c色着色，则必须有一行，列等长度为n的所有单元格都具有相同的颜色。那就是：多人n排字游戏不能以平局结束，无论n有多大，有多少人在玩，如果您在棋盘上有足够多的人玩尺寸。 Hales-Jewett定理隐含了Van der Waerden定理。

舒尔定理

对于任何给定的c，都有一个数字N，如果数字1，2，...，N用c种不同的颜色着色，那么必须有一对整数x，y，使得x，y和x + y都是相同的颜色。存在该定理的许多概括，包括Rado定理，Rado-Folkman-Sanders定理，Hindman定理和Milliken-Taylor定理。格雷厄姆，罗斯柴尔德和斯宾塞是拉姆齐理论中这些以及其他许多结果的经典参考。

结果

Ramsey理论的结果通常具有两个主要特征。首先，它们是非建设性的：它们可能表明存在某种结构，但没有给出寻找此结构的过程（除了蛮力搜索）。例如，鸽洞原理就是这种形式。其次，尽管拉姆齐理论的结果确实表明足够大的物体必须一定包含给定的结构，但这些结果的证明通常要求这些物体非常大-呈指数增长或甚至与阿克曼函数一样快的界线并不罕见。在许多情况下，这些界限是证明的伪像，尚不清楚是否可以对其进行实质性的改进。在其他情况下，已知任何边界都必须非常大，有时甚至比任何原始递归函数还要大；有关示例，请参见Paris-Harrington定理。格雷厄姆数是认真的数学证明中使用的最大数，是与拉姆齐理论有关的问题的上限。

Ramsey理论中的定理通常是三种类型之一。许多定理以Ramsey定理本身为模型，它们断言在一个大型结构化对象的每个分区中，其中一个类必然包含一个大型结构化子对象，但没有提供有关这是哪个类的信息。有时，出现此类Ramsey类型结果的原因是最大的分区类始终包含所需的子结构。根据图兰定理，这种结果称为密度结果或图兰类型结果。著名的例子包括Szemerédi定理，它是对van der Waerden定理的强化，以及Hales-Jewett定理的密度形式。

拉姆齐数

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

对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；

在着色理论中是这样描述的：对于完全图Kn的任意一个2边着色(e1,e2)，使得Kn[e2]中含有一个k边形，Kn[e1]含有一个l边形，则称满足这个条件的最小的n为一个拉姆齐数。（注意：Ki按照图论的记法表示i阶完全图）

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

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

对于完全图Kn的每条边都任意涂上r种颜色之一，分别记为 e1,e2,e3,...,er ，在Kn中，必定有个颜色为e1的l1边形，或有个颜色为e2的l2边形……或有个颜色为er的lr边形。符合条件又最少的数n则记为R(l1,l2,l3,...,lr;r)。

拉姆齐数的数值或上下界

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

已知的拉姆齐数

R(3,3)=6,R(3,4)=R(4,3)=9,R(3,5)=R(5,3)=14,R(3,6)=R(6,3)=18,R(3,7)=R(7,3)=23,R(3,8)=R(8,3)=28

R(3,9)=R(9,3)=36,R(4,4)=18,R(4,5)=R(5,4)=25