关键字搜索:
快速导航
Ramsey定理
发布时间: 2019-06-11       浏览次数:

  确定一般的Ramsey数rt(q1,q2,…,qk)是一个坚苦的工做。关于它们的精确值我们晓得得很少。但不难看出,rt(t,q2,…,qk)=rt(q2,…,qk)而且q1,q2,…,qk的陈列挨次不影响Ramsey数的值。

  Ramsey证明,对于给定的正整数数k及l,R(k,l)的谜底是独一和无限的。目前的进展如下图所示(良多只要一个范畴):

  虽然R(3,3)的证明十分巧妙,可是现实上已知的Ramsey数很是少,好比R(3,3)=6,R(3,4)=9,R(4,4)=18保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度:

  声明:百科词条人人可编纂,词条建立和点窜均免费,毫不存正在及代办署理商付费代编,请勿上当。详情

  按照抽屉道理,Friend和Strange中有一个调集至多有3小我,不妨假设是调集Friend。

  Friend中3小我P,Q,R若是相互互相不认识,则问题已获得证明。不然有两小我互相认识,不妨设这两小我是P和Q,则A,P,Q这3小我相互认识。

  一对a和b,对应于一个整数r,使得r小我中或有a小我彼此认识,或有b小我互不认识;或有a小我互不认识,或有b小我彼此认识。这个数r的最小值用R(a,b)来暗示,也就是R(a,b)个极点的完全图。用红蓝两种颜色进行着色,无论何种环境必至多存正在以下两者之一:(1)一个a个极点着红颜色的完全子图,或一个b个极点着蓝颜色的完全子图;(2)一个a个极点着蓝颜色的完全子图,或一个b个极点着红颜色的完全子图。

  假设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定理是鸽巢道理的加强版的扩展。

  若把以上会商中红、蓝两种颜色改为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)暗示。

  给定整数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)。

  (2)证明9小我中若不是3小我互不认识,则必有4小我互相认识,同样,9小我中若不是3小我互相认识,则必有4小我互不认识。

  针对Ramsey定理扩展到肆意多种颜色的环境,我们给出一个很是简单的引见。若是n1,n2和n3都是大于或等于2的整数,则存正在整数p,使得Kp→Kn1,Kn2,Kn3。

  Ramsey F P. On a Problem of Formal Logic[J]. Proceedings of the London Mathematical Society, 2009, 30(1):1-24.

  由抽屉道理可知:这五条线段中至多有是同色的。不妨设AB、AC、AD为红色。若BC或CD为红色,则结论明显成立。若BC和CD均为蓝色,则若BD为红色,则必然有三小我彼此认识;若BD为蓝色,则必然有三小我互相不认识。

  上述问题能够看做是R(3,3)=6的一个特例,的证明操纵图的抽象而曲不雅的特点,证了然R(3,3)=6。

  因而,K17→K3,K3,K3,而K16→K3,K3,K3。我们能够用雷同的方义Ramsey数r(n1,n2,…,nk),而对于点对Ramsey定理的完全一般形式是这些数存正在;即存正在整数p,使得Kp→Kn1,Kn2,…,Knk成立。

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

  注:关于以上推论和定理的证明,能够参考《组合数学(第4版)》卢开澄、卢华明编著,此中的第3章第15节给取了证明

  Frank Plumpton Ramsey(弗兰克·普伦普顿·拉姆齐,1903-1930)是英国

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

  定理4对所有的整数a和b,a,b=2,若R(a,b-1)和R(a-1,b)是偶数,则

  注:这个定理以弗兰克·普伦普顿·拉姆齐定名,1930年他正在论文On a Problem in Formal Logic

  “想像有队外星人戎行正在地球下降,要求取得R(5,5)的值,不然便会地球。正在这个环境,我们该当集中所有电脑和数学家测验考试去找这个数值。若它们要求的是R(6,6)的值,我们要测验考试这班外星人了。”

  Ramsey定理还有更一般的形式,正在这种形式中点对(两个元素的子集)换成了t个元素的子集,此中t≥1是某个整数。令Ktn暗示n元素调集中所有t个元素的子集的调集。将的概念扩展,Ramsey定理的一般形式可论述如下:

  若是调集Strange至多有3小我,能够同样会商如下:若Strange有3人L,M,N相互互相认识,则问题的前提已获得满脚。不然设L和M互不了解,则A,L,M互不了解。

  证明如下:起首,把这6小我设为A、B、C、D、E、F六个点。由A点能够引出AB、AC、AD、AE、AF五条线段。设:若是两小我认识,则设这两小我构成的线段为红色;若是两小我不认识,则设这两小我构成的线段为蓝色。