拉姆齐数的研究论文

一对常数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数的值。

西塔潘猜想，又称“拉姆齐二染色定理”，是由英国数理逻辑学家西塔潘于上个世纪90年代提出的一个猜想。在组合数学上，拉姆齐（Ramsey）定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。2011年5月，由北京大学、南京大学和浙江师范大学联合举办的逻辑学术会议在浙江师范大学举行，中南大学数学科学与计算技术学院酷爱数理逻辑的刘嘉忆的报告给这一悬而未决的公开问题一个否定式的回答，彻底解决了西塔潘的猜想。来源于“拉姆齐二染色定理”以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的一个问题》）证明了R(3,3)=6。拉姆齐数的定义拉姆齐数，用图论的语言有两种描述：对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；在着色理论中是这样描述的：对于完全图Kn的任意一个2边着色(e1,e2)，使得Kn[e1]中含有一个k阶子完全图，Kn[e2]含有一个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(1,s)=1， R(2,s)=s， R(l1,l2,l3,...,lr;r)=R(l2,l1,l3,...,lr;r)=R(l3,l1,l2,...,lr;r)（将li的顺序改变并不改变拉姆齐的数值）。r,s 3 4 5 6 7 8 9 103 6 9 14 18 23 28 36 40 – 434 9 18 25 35 – 41 49 – 61 56 – 84 73 – 115 92 – 1495 14 25 43 – 49 58 – 87 80 – 143 101 – 216 125 – 316 143 – 4426 18 35 – 41 58 – 87 102 – 165 113 – 298 127 – 495 169 – 780 179 – 11717 23 49 – 61 80 – 143 113 – 298 205 – 540 216 – 1031 233 – 1713 289 – 28268 28 56 – 84 101 – 216 127 – 495 216 – 1031 282 – 1870 317 – 3583 317 – 60909 36 73 – 115 125 – 316 169 – 780 233 – 1713 317 – 3583 565 – 6588 580 – 1267710 40 – 43 92 – 149 143 – 442 179 – 1171 289 – 2826 317 – 6090 580 – 12677 798 – 23556R(3,3,3)=17 R(3,3)等于6的证明证明：在一个K6的完全图内，每边涂上红或蓝色，必然有一个红色的三角形或蓝色的三角形。任意选取一个端点P，它有5条边和其他端点相连。根据鸽巢原理，3条边的颜色至少有两条相同，不失一般性设这种颜色是红色。在这3条边除了P以外的3个端点，它们互相连结的边有3条。若这3条边中任何一条是红色，这条边的两个端点和P相连的2边便组成一个红色三角形。若这3条边中任何一条都不是红色，它们必然是蓝色，因此，它们组成了一个蓝色三角形。而在K5内，不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点的线是红色，和其余两个端点的连线是蓝色即可。这个定理的通俗版本就是友谊定理。编辑本段相关研究2010年8月，中南大学数学科学与计算技术学院酷爱数理逻辑的刘嘉忆在自学反推数学的时候，第一次接触到拉姆齐二染色定理，并在阅读大量文献时发现，海内外不少学者都在进行反推数学中的拉姆齐二染色定理的证明论强度的研究。这是由英国数理逻辑学家西塔潘于上个世纪90年代提出的一个猜想，10多年来许多著名研究者一直努力都没有解决。同年10月的一天，刘嘉忆突然想到利用之前用到的一个方法稍作修改便可以证明这一结论，连夜将这一证明写出来，投给了数理逻辑国际权威杂志《符号逻辑杂志》。2011年5月，由北京大学、南京大学和浙江师范大学联合举办的逻辑学术会议在浙江师范大学举行，还是大三学生的刘嘉忆应邀参加了这次会议，报告了他对目前反推数学中的拉姆齐二染色定理的证明论强度的研究。刘嘉忆的报告给这一悬而未决的公开问题一个否定式的回答，彻底解决了西塔潘的猜想。《符号逻辑杂志》的主编、逻辑学专家、芝加哥大学数学系邓尼斯·汉斯杰弗德看到论文后给他写信：“我是过去众多研究该问题而无果者之一，看到这一问题的最终解决感到非常高兴，特别如你给出的如此漂亮的证明，请接受我对你令人赞叹的惊奇的成果的祝贺！”同时，邓尼斯·汉斯杰弗德教授高兴地将刘嘉忆的研究介绍给了其他几位同仁和专家，他们一起审读、反复商讨。论文审稿人、芝加哥大学博士达米尔·扎法洛夫也认为：“这是一个重要的结果，过去20多年许多著名科研工作者在这方面进行努力。该问题的研究促进了反推数学和计算性理论方面的研究。”2011年9月16日，美国芝加哥大学数理逻辑学术会议上，云集了来自欧美的许多数理逻辑专家、学者。大会邀请了12位专家、学者作学术报告，刘嘉忆作为亚洲高校唯一一位代表在会上作了40分钟报告。他在数理逻辑方面的研究成果，让与会专家、学者对这位来自中国的“80后”投上赞许的目光。刘嘉忆表示，他投给《美国数学会汇刊》的论文获得威士康星大学、伯克利大学等几位教授很高的评价，有望公开发表。

西塔潘猜想是由英国数理逻辑学家西塔潘于20世纪90年代提出的一个反推数学领域关于拉姆齐二染色定理证明强度的猜想。拉姆齐二染色定理以弗兰克·普伦普顿·拉姆齐正式命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的一个问题》）证明了R(3,3)=61930年，英国数学家弗兰克·普伦普顿·拉姆齐在一篇题为《形式逻辑上的一个问题》的论文中证明了R(3,3)=6。这条定理被命名为“拉姆齐二染色定理”。用文字来表述就是“要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识，这个数n记为R(k,l)”。拉姆齐二染色定理的通俗版本被称为“友谊定理”，即在一群不少于6人的人中，或者有3人，他们互相都认识；或者有3人，他们互相都不认识。 拉姆齐二染色定理（Ramsey Theorem for Pair）用非形式的语言可以叙述为任何一个对边进行2-染色的含（可数）无穷个顶点的完全图都有一个单一染色的含有无穷个顶点的子完全图，而弱柯尼希定理（Weak König Lemma）则是说任何一个（可数）无穷二叉树都有一条无穷长的路径。这两条都是二阶算术中的陈述，说的是一个类中满足某种性质的子集存在，可以粗暴地认为它们在某种程度上都是在表现或者替代二阶算术中的选择公理（Axiom of Choice）（一般的“Axiom of Choice”可对超出可数无穷多的对象进行选择）。 在反推数学中，研究的其实是二阶算术的各个子系统以及它们的强度关系，而最重要的是被称为 Big Five的五个子系统 RCA 0 , WKL 0 , ACA 0 （后面两个与本猜想无关，故不列出）。其中 WKL 0 是基本系统 RCA 0 添加弱柯尼希定理的系统，而 RCA 0 添加拉姆齐二染色定理的系统被称为 RT2 2 (不在Big Five，类似还有 RT3 2 ，在此不表)。经过若干数学家的研究，他们发现了一些子系统间存在强弱的比较关系：和 RT2 2 形式接近的 RT3 2 比 ACA 0 要强(其实一样)，而 RT2 2 则不比 ACA 0强，（ ACA 0 比 WKL 0 强是基本的）等等[1]，从这些结果，他们隐约认为 RT22 和 WKL 0 的强度是可以比较的，1995年英国数理逻辑学家西塔潘在一篇论文[2]中发现WKL_0并不强于 RT2 2 ，于是他猜测可能 RT2 2 要强于 WKL 0。 这一猜想引发了大量研究，困扰了许多数学家十多年之久，直到刘路的出现，他证明了 RT2 2并不包含 WKL 0 ，从而给该猜想一个否定的回答。 拉姆齐数的定义拉姆齐数，用图论的语言有两种描述：对于所有的N顶图，包含k个项的团或l个项的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；在着色理论中是这样描述的：对于完全图Kn的任意一个2边着色(e1,e2)，使得Kn[e1]中含有一个k阶子完全图，Kn[e2]含有一个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)。[2]拉姆齐数的数值已知的拉姆齐数非常少，保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度：“想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了。”反推数学反推数学是数理逻辑的一个小分支。在上世纪80、90年代，反推数学还比较活跃。 上一个十年中，有些衰落。目前，又有了一点生气。现在，全球研究人员估计超过二十人。国内南京大学对反推数学有研究。 反推数学大致是这样的：通常的数学大致是从公理到定理的研究，而反推数学则是从定理（陈述）到公理的研究，二者正好方向相反。 举一个可能有些不恰当的例子，如果知道 X = 3 这一条件，那么我们可以推出 X^2 = 9 ，这就是通常的数学。但是如果我们知道 X^2 = 9 而要问什么条件可以保证这个结论成立的话，那么选择可就多了，X = 3 可以，X = -3 可以，X + 1 = 4，X - 1 = 2等等也都可以，不过我们或许会特别注意 | X | = 3 ，因为感觉这样“不多也不少”，而其余的则感觉有所遗漏。容易发现 X = 3 和 X^2= 9 这两个陈述的蕴意是有所差别的，当然这也是有语境的，我们自然认定是在全体整数或者实数的范围中考虑的，如果我们是在正数的范围中考虑，那么那两个陈述的蕴意则恰好相当，没有差别。 这个例子很简单，因为其中的陈述看起来很简单，它们的蕴意比较起来很容易。如果我们的陈述是实数的确界定理和闭区间套定理，那么要判断这两个陈述的蕴意就要麻烦一些，对于可能更复杂的两个陈述，判断起来则更不容易。可以说，反推数学就是要探讨（在一个基本体系中）一个陈述的精确蕴意(专业的词汇是证明论强度)，既不能多一点也不能少一点。为求精确，最好还是用一些符号：存在一个基本体系 S 以及一个陈述 T （它不能被 S 所证），目标是要在 S 上添加适当的公理（也有可能是一些规则），使得新的体系S’恰好能证出T，“恰好”体现为一则 S’ 要能证出 T ，二则同时 S 和 T 本身就蕴含 S’。编辑本段拉姆齐二染色定理来源这个定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的一个问题》）证明了R(3,3)=6。拉姆齐数的定义拉姆齐数，用图论的语言有两种描述：对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；在着色理论中是这样描述的：对于完全图Kn的任意一个2边着色(e1,e2)，使得Kn[e1]中含有一个k阶子完全图，Kn[e2]含有一个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(1,s)=1， R(2,s)=s， R(l1,l2,l3,...,lr;r)=R(l2,l1,l3,...,lr;r)=R(l3,l1,l2,...,lr;r)（将li的顺序改变并不改变拉姆齐的数值）。[3] r,s 3 4 5 6 7 8 9 103 6 9 14 18 23 28 36 40 – 434 9 18 25 35 – 41 49 – 61 56 – 84 73 – 115 92 – 1495 14 25 43 – 49 58 – 87 80 – 143 101 – 216 125 – 316 143 – 4426 18 35 – 41 58 – 87 102 – 165 113 – 298 127 – 495 169 – 780 179 – 11717 23 49 – 61 80 – 143 113 – 298 205 – 540 216 – 1031 233 – 1713 289 – 28268 28 56 – 84 101 – 216 127 – 495 216 – 1031 282 – 1870 317 – 3583 317 – 60909 36 73 – 115 125 – 316 169 – 780 233 – 1713 317 – 3583 565 – 6588 580 – 1267710 40 – 43 92 – 149 143 – 442 179 – 1171 289 – 2826 317 – 6090 580 – 12677 798 – 23556R(3,3,3)=17 R(3,3)等于6的证明证明：在一个K6的完全图内，每边涂上红或蓝色，必然有一个红色的三角形或蓝色的三角形。任意选取一个端点P，它有5条边和其他端点相连。根据鸽巢原理，3条边的颜色至少有两条相同，不失一般性设这种颜色是红色。在这3条边除了P以外的3个端点，它们互相连结的边有3条。若这3条边中任何一条是红色，这条边的两个端点和P相连的2边便组成一个红色三角形。若这3条边中任何一条都不是红色，它们必然是蓝色，因此，它们组成了一个蓝色三角形。而在K5内，不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点的线是红色，和其余两个端点的连线是蓝色即可。这个定理的通俗版本就是友谊定理

西塔潘猜想是对拉姆齐二染色定理的证明强度研究的一个猜想。拉姆齐二染色定理是以数学家弗兰克·普伦普顿·拉姆齐命名。1930年他在论文On a Problem in Formal Logic（《形式逻辑上的一个问题》）证明了R(3,3)=6。拉姆齐数的定义拉姆齐数，用图论的语言有两种描述：对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)；在着色理论中是这样描述的：对于完全图Kn的任意一个2边着色(e1,e2)，使得Kn[e1]中含有一个k阶子完全图，Kn[e2]含有一个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)。