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的一个特例,上面的证明利用图的形象而直观的特点,证明了R(3,3)=6。
下面不用图给出R(3,3)=6的证明:
对于A以外的5个人可分为Friend和Strange两个集合。
Friend=其余5人中与A互相认识的集合;
Strange=其余5人中与A互相不认识的集合。
根据抽屉原理,Friend和Strange中有一个集合至少有3个人,不妨假设是集合Friend。
Friend中3个人P,Q,R若是彼此互相不认识,则问题已得到证明。否则有两个人互相认识,不妨设这两个人是P和Q,则A,P,Q这3个人彼此认识。
若是集合Strange至少有3个人,可以同样讨论如下:若Strange有3人L,M,N彼此互相认识,则问题的条件已得到满足。否则设L和M互不相识,则A,L,N互不相识。
可以把推理过程形象地表示,如图所示:
虽然R(3,3)的证明十分巧妙,但是实际上已知的Ramsey数非常少,比如R(3,3)=6,R(3,4)=9,R(4,4)=18保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度:
“想像有队外星人军队在地球降落,要求取得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数的值。
Ramsey条纹的物理原理
分离振荡场。Ramsey条纹它让热原子束通过微波腔获得干涉条纹,这样的结构中用到了前面提到的分离振荡场,也称之为ramsey作用,这就是他的原理。
Ramsey定理的介绍
FrankPlumptonRamsey(弗兰克·普伦普顿·拉姆齐,1903-1930)是英国1哲学家、数学家、经济学家,26岁英年早逝,对经济学纯理论是一个重大损失,尽管他的主要兴趣在哲学和数理逻辑方面。关于他的身份,也是十分高贵的,他是剑桥皇家学院会员、温彻斯特和三一学院昔日的学者、马格达兰校长之子。在组合数学中的Ramsey定理,又称拉姆齐二染色定理,涉及Ramsey数和Ramsey问题,关于Ramsey问题有一个广泛流传的例子,即世界上任意6个人中,总有3个人相互认识,或互相皆不认识。