Ramsey定理数学定理

Ramsey(1903~1930)是英国数理逻辑学家，他把抽屉原理加以推广，得出广义抽屉原理，也称为Ramsey定理。Ramsey定理一般通过用两种颜色为一个N阶完全图着色（二染色）来解释。

中文名

广义抽屉原理

外文名

Ramsey定理

别称

抽屉原理

表达式

任意六个人中至少三个人认识或不认识

提出者

Ramsey

应用学科

数学

适用领域范围

数学

相关术语

Ramsey数

一对常数a和b,对应于一个整数r,使得r个人中或有a个人相互认识，或有b个人互不认识；或有a个人互不认识，或有b个人相互认识，这个数r的最小值用R(a,b)来表示，也就是R(a,b)个顶点的完全图，用红蓝两种颜色进行着色,无论何种情况必至少存在以下两者之一：(1)一个a个顶点着红颜色的完全子图，或一个b个顶点着蓝颜色的完全子图；(2)一个a个顶点着蓝颜色的完全子图，或一个b个顶点着红颜色的完全子图。

上述问题可以看作是R(3,3)=6的一个特列。

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

Ramsey证明，对于给定的正整数数k及l，R(k,l)的答案是唯一和有限的。

一般的Ramsey数

若把以上讨论中红、蓝两种颜色改为k种颜色c1,c2,...,ck，把存在a条边的同色完全图，或b条边的同色完全图，改为或a1,或a2,...，或a条边的同色完全图，即得到Ramsey数R(a1,a2,...,ak)，即对r个顶点的完全图，用k种颜色c1,c2,...,ck任意染色，必然是或出现以c1颜色的a1个顶点的完全图,或出现以c2颜色的a2个顶点的完全图，...,或出现以ck颜色的ak个顶点的完全图，这样的整数r的最小值用R(a1,a2,...ak)表示。

针对Ramsey定理扩展到任意多种颜色的情况，我们给出一个非常简略的介绍。如果n1，n2和n3都是大于或等于2的整数，则存在整数p，使得Kp→Kn1，Kn2，Kn3。

也就是说，如果把Kp的每条边着上红色、蓝色或绿色，那么或者存在一个红Kn1，或者存在一个蓝Kn2，或者存在一个绿Kn3。使该结论成立的最小整数p称为Ramsey数r(n1，n2，n3)。已知这种类型的仅有的非平凡Ramsey数为r(3，3，3)=17。

因此，K17→K3，K3，K3，而K16→K3，K3，K3。我们可以用类似的方法定义Ramsey数r(n1，n2，…，nk)，而对于点对Ramsey定理的完全一般形式是这些数存在；即存在整数p，使得Kp→Kn1，Kn2，…，Knk成立。

Ramsey定理还有更一般的形式，在这种形式中点对（两个元素的子集）换成了t个元素的子集，其中t≥1是某个整数。令Ktn表示n元素集合中所有t个元素的子集的集合。将上面的概念扩展，Ramsey定理的一般形式可叙述如下：

给定整数t≥2及整数q1，q2，…，qk≥t，存在一个整数p，使得Ktp→Ktq1，Ktq2，…，Ktqk成立。也就是说，存在一个整数p，使得如果给p元素集合中的每一个t元素子集指定k种颜色c1，c2，…，ck中的一种，那么或者存在q1个元素，这些元素的所有t元素子集都被指定为颜色c1，或者存在q2个元素，这些元素的所有t元素子集都被指定为颜色c2，…，或者存在qk个元素，它的t元素子集都被指定为颜色ck。这样的整数中最小的整数p为Ramsey数rt(q1，q2，…，qk)。

假设t=1。于是，r1(q1，q2，…，qk)就是满足下面条件的最小的数p：如果p元素集合的元素被用颜色c1，c2，…，ck中的一种颜色着色，那么或者存在q1个都被着成颜色c1的元素，或者存在q2个都被着成颜色c2的元素，…，或者存在qk个都被着成颜色ck的元素。因此，根据鸽巢原理的加强版，有r1(q1，q2，…，qk)=q1+q2+…+qk-k+1这就证明Ramsey定理是鸽巢原理的加强版的扩展。

确定一般的Ramsey数rt(q1，q2，…，qk)是一个困难的工作。关于它们的准确值我们知道得很少。但不难看出，rt(t，q2，…，qk)=rt(q2，…，qk)并且q1，q2，…，qk的排列顺序不影响Ramsey数的值。

参考资料

1.拉姆齐定理（Ramsey"s Theorem）·DNC"s Not a Coder