这个定理以弗兰克·普伦普顿·拉姆齐命名 ， 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月 ， 由北京大学、南京大学和浙江师范大学联合举办的逻辑学术会议在浙江师范大学举行 ， 还是大三学生的刘嘉忆应邀参加了这次会议 ， 报告了他对目前反推数学中的拉姆齐二染色定理的证明论强度的研究 。 刘嘉忆的报告给这一悬而未决的公开问题一个否定式的回答 ， 彻底解决了西塔潘的猜想 。

• 有一种幸福叫回忆,有一种思念叫想你是什么歌 有一种幸福叫回忆
• 撒贝宁照片式记忆是真的吗 撒贝宁照片
• 描写美好回忆的词语 描写十一月美好的词语
• 360浏览器输入框记忆功能？ Windows 7旗舰版系统下浏览器网页输入框无法输入文字
• 已经2020年了，你对张国荣的记忆还有多少？
• 一座城市一段回忆说说 到一座城市的心情说说
• 微信面对面建群怎么加入图片 微信面对面建群怎么加入
• 补脑良药金标状元汤，增强记忆力，心肾同调
• 如何改善孩子记忆力?试试DHA藻油软糖吧
• 李振辉回忆李小龙 李振辉