刘嘉忆(刘嘉忆面对面)

刘嘉忆(刘嘉忆面对面)

22岁数学天才刘路（刘嘉忆）在Journal of Symbolic Logic刊物上所发表的文章叫什么名？

名字是《RT22 DOES NOT IMPLY WKL0》，百度文库中第一个搜索“西塔潘猜想”的就是这篇论文。

因为公式无法表达，我写了前22是RT的下标，最后0是WKL的下标。

你可以看到它，但如果你不专攻数学，你就无法理解它。

反正我的高等数学也不差。我考研考了140分以上，却完全看不懂他的证明过程。

这么说吧，他真的很棒。你好！

名字是《RT22 DOES NOT IMPLY WKL0》。百度搜索“西塔潘猜想”就能找到。前22是下标。

你对我的回答满意吗~ ~锥避免分区量内不可枚举树诱导的闭集，太难了。

拉姆齐二染色定理是什么

拉姆齐着色定理是一个数学组合问题，其命题如下：

要找到这样一个最小数n，必须有k个互相认识的人或者l个互相不认识的人。

这个定理是以弗兰克拉姆齐的名字命名的，他在1930年关于形式逻辑中一个问题的论文(《形式逻辑上的一个问题》)中证明了R(3，3)=6。这个证据有一张图纸。

-

在组合数学中，拉姆齐定理是为了解决以下问题：要找到这样一个最小数n，必须有k个互相认识的人或者l个互相不认识的人。

这个定理是以弗兰克拉姆齐的名字命名的，他在1930年关于形式逻辑中一个问题的论文(《形式逻辑上的一个问题》)中证明了R(3，3)=6。

拉姆齐数的定义

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

对于所有的n顶点图，都有k个顶点的组或l个顶点的独立集。具有这种性质的最小自然数n称为拉姆齐数，记录为R (k，l)。

在着色理论中，是这样描述的：对于完全图Kn的任意两条边着色(e1，e2)，如果Kn[e1]包含一个K阶的次完全图，Kn[e2]包含一个L阶的次完全图，那么满足这个条件的最小n叫做一个Ramsey数。(注：Ki根据图论的记数法表示I阶完全图)

拉姆齐证明了给定正整数k和l，R(k，l)的答案是唯一且有限的。

拉姆齐数也可以扩展到两个以上的数：

完整图形Kn的每条边被任意地涂上一种R色，记录为e1，e2，e3，分别是。在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的顺序不会改变Ramsey的数值)。

r，s345678910

369141823283640 43

49182535 4149 6156 8473 11592 149

5142543 4958 8780 143101 216125 316143 442

61835 4158 87102 165113 298127 495169 780179 1171

72349 6180 143113 298205 540216 1031233 1713289 2826

82856 84101 216127 495216 1031282 1870317 3583317 6090

93673 115125 316169 78023

3 – 1713317 – 3583565 – 6588580 – 12677

1040 – 4392 – 149143 – 442179 – 1171289 – 2826317 – 6090580 – 12677798 – 23556

R(3,3,3)=17

更详尽的可见于www.combinatorics.org/Surveys/ds1/sur.pdf

R(3,3)等于6的证明

证明：在一个K6的完全图内，每边涂上红或蓝色，必然有一个红色的三角形或蓝色的三角形。

任意选取一个端点P，它有5条边和其他端点相连。

根据鸽巢原理，3条边的颜色至少有两条相同，不失一般性设这种颜色是红色。

在这3条边除了P以外的3个端点，它们互相连结的边有3条。

若这3条边中任何一条是红色，这条边的两个端点和P相连的2边便组成一个红色三角形。

若这3条边中任何一条都不是红色，它们必然是蓝色，因此，它们组成了一个蓝色三角形。

而在K5内，不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点 的线是红色，和其余两个端点的连线是蓝色即可。这个定理的通俗版本就是友谊定理。

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－提个问题花多少时间，我百度搜关键字 ‘拉姆齐二染色定理’ 的第一个竟然显示你这个问题！！ 第二个就是

拉姆齐二染色定理的百科你不会看一下， 你能告诉我你们这种人都脑子都在想什么么？西塔潘猜想，又称“拉姆齐二染色定理”，是由英国数理逻辑学家西塔潘于上个世纪90年代提出的一个猜想。在组合数学上，拉姆齐（ramsey）定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。2011年5月，由北京大学、南京大学和浙江师范大学联合举办的逻辑学术会议在浙江师范大学举行，中南大学数学科学与计算技术学院酷爱数理逻辑的刘嘉忆的报告给这一悬而未决的公开问题一个否定式的回答，彻底解决了西塔潘的猜想。

西塔潘猜想是由英国数理逻辑学家西塔潘于20世纪90年代提出的一个猜想。但定理以弗兰克·普伦普顿·拉姆齐正式命名，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)。[2] 拉姆齐数的数值或上下界 已知的拉姆齐数非常少，保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度：“想像有队外星人军队在地球降落，要求取得r(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是r(6,6)的值，我们要尝试毁灭这班外星人了。”,你看看这个，联系他，他给出了否定的答案。在组合数学上，拉姆齐（Ramsey）定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。

这个定理以弗兰克·普伦普顿·拉姆齐命名，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多年许多著名科研工作者在这方面进行努力。该问题的研究促进了反推数学和计算性理论方面的研究。”湖南中南大学的一个大三的本科生已经解决了这个问题。