一 : 拉姆齐定理：拉姆齐定理-名称，拉姆齐定理-简介

中南大学数学科学与计算技术学院2008级本科生刘嘉忆破解拉姆齐(ramsly)二染色定理。拉姆齐(ramsly)二染色定理是由英国数理逻辑学家Seetapun于上个世纪90年代提出的一个猜想，十多年来，许多著名研究者一直努力都没有解决。刘嘉忆的报告给拉姆齐(ramsly)二染色定理这一悬而未决的公开问题一个否定式的回答，彻底解决了Seetapun对拉姆齐(ramsly)二染色定理的猜想。

拉姆齐理论_拉姆齐定理 -名称

拉姆齐定理

拉姆齐理论_拉姆齐定理 -简单介绍

在组合数学上，拉姆齐(Ramsey)定理是要解决以下的问题：要找这样1个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。
这个定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的1个问题》）证明了R(3,3)=6。
拉姆齐数的定义
拉姆齐数，用图论的语言有2种描述：
对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为1个拉姆齐数，记作R(k,l)；
在着色理论中是这样描述的：对于完全图Kn的任意1个2边着色(e1,e2)，使得Kn【e1】中含有1个k边形，Kn【e1】含有1个l边形，则称满足这个条件的最小的n为1个拉姆齐数。（注意：Ki按照图论的记法表示i阶完全图）
拉姆齐证明，对与给定的正整数数k及l，R(k,l)的答案是唯一和有限的。
拉姆齐数亦可推广到多于2个数：
对于完全图Kn的每条边都任意涂上r种颜色之一，分别记为 e1,e2,e3,...,er ，在Kn中，必定有个颜色为e1的l1边形，或有个颜色为e2的l2边形……或有个颜色为er的lr边形。符合条件又最少的数n则记为R(l1,l2,l3,...,lr;r)。
拉姆齐数的数值或上下界
已知的拉姆齐数非常少，保罗·艾狄胥曾以1个故事来描述寻找拉姆齐数的难度：“想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况[www.61k.com)，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是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的顺序改变并不改变拉姆齐的数值）

二 : 拉姆齐定理：拉姆齐定理-名称，拉姆齐定理-简介

中南大学数学科学与计算技术学院2008级本科生刘嘉忆破解拉姆齐(ramsly)二染色定理。拉姆齐(ramsly)二染色定理是由英国数理逻辑学家Seetapun于上个世纪90年代提出的一个猜想，十多年来，许多著名研究者一直努力都没有解决。刘嘉忆的报告给拉姆齐(ramsly)二染色定理这一悬而未决的公开问题一个否定式的回答，彻底解决了Seetapun对拉姆齐(ramsly)二染色定理的猜想。

拉姆齐二染色定理_拉姆齐定理 -名称

拉姆齐定理

拉姆齐二染色定理_拉姆齐定理 -简单介绍

在组合数学上，拉姆齐(Ramsey)定理是要解决以下的问题：要找这样1个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。
这个定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文On a Problem in Formal Logic（《形式逻辑上的1个问题》）证明了R(3,3)=6。
拉姆齐数的定义
拉姆齐数，用图论的语言有2种描述：
对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为1个拉姆齐数，记作R(k,l)；
在着色理论中是这样描述的：对于完全图Kn的任意1个2边着色(e1,e2)，使得Kn【e1】中含有1个k边形，Kn【e1】含有1个l边形，则称满足这个条件的最小的n为1个拉姆齐数。（注意：Ki按照图论的记法表示i阶完全图）
拉姆齐证明，对与给定的正整数数k及l，R(k,l)的答案是唯一和有限的。
拉姆齐数亦可推广到多于2个数：
对于完全图Kn的每条边都任意涂上r种颜色之一，分别记为 e1,e2,e3,...,er ，在Kn中，必定有个颜色为e1的l1边形，或有个颜色为e2的l2边形……或有个颜色为er的lr边形。符合条件又最少的数n则记为R(l1,l2,l3,...,lr;r)。
拉姆齐数的数值或上下界
已知的拉姆齐数非常少，保罗·艾狄胥曾以1个故事来描述寻找拉姆齐数的难度：“想像有队外星人军队在地球降落，要求取得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）定理是要解决以下的问题：要找这样一个最小的数n，使得n个人中必定有k个人相识或l个人互不相识。

拉姆齐二染色定理_拉姆齐二染色定理 -来源

拉姆齐二染色定理以弗兰克·普伦普顿·拉姆齐命名，1930年他在论文OnaProbleminFormalLogic（《形式逻辑上的1个问题》）证明了R(3,3)=6。

拉姆齐二染色定理_拉姆齐二染色定理 -相关概念

拉姆齐二染色定理

拉姆齐数的定义

拉姆齐数，用图论的语言有2种描述：对于所有的N顶图，包含k个顶的团或l个顶的独立集。具有这样性质的最小自然数N就称为1个拉姆齐数，记作R(k,l)；在着色理论中是这样描述的：对于完全图Kn的任意1个2边着色(e1,e2)，使得Kn[e1]中含有1个k阶子完全图，Kn[e2]含有1个l阶子完全图，则称满足这个条件的最小的n为1个拉姆齐数。（注意：Ki按照图论的记法表示i阶完全图）拉姆齐证明，对与给定的正整数数k及l，R(k,l)的答案是唯一和有限的。

拉姆齐数亦可推广到多于2个数

对于完全图Kn的每条边都任意涂上r种颜色之一，分别记为e1,e2,e3,...,er，在Kn中，必定有个颜色为e1的l1阶子完全图，或有个颜色为e2的l2阶子完全图……或有个颜色为er的lr阶子完全图。符合条件又最少的数n则记为R(l1,l2,l3,...,lr;r)。

拉姆齐数的数值或上下界

已知的拉姆齐数非常少，保罗·艾狄胥曾以1个故事来描述寻找拉姆齐数的难度：“想像有队外星人军队在地球降落，要求取得R(5,5)的值，否则便会毁灭地球。在这个情况，我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值，我们要尝试毁灭这班外星人了。”

r,s345678910369141823283640 – 4349182535 – 4149 – 6156 – 8473 – 11592 – 1495142543 – 4958 – 8780 – 143101 – 216125 – 316143 – 44261835 – 4158 – 87102 – 165113 – 298127 – 495169 – 780179 – 117172349 – 6180 – 143113 – 298205 – 540216 – 1031233 – 1713289 – 282682856 – 84101 – 216127 – 495216 – 1031282 – 1870317 – 3583317 – 609093673 – 115125 – 316169 – 780233 – 1713317 – 3583565 – 6588580 – 126771040 – 4392 – 149143 – 442179 – 1171289 – 2826317 – 6090580 – 12677798 – 23556

拉姆齐二染色定理_拉姆齐二染色定理 -证明

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

证明：在1个K6的完全图内，每边涂上红或蓝色，必然有1个红色的三角形或蓝色的三角形。任意选取1个端点P，它有5条边和其他端点相连。根据鸽巢原理，3条边的颜色至少有两条相同，不失一般性设这种颜色是红色。在这3条边除了P以外的三个端点，它们互相连结的边有3条。若这3条边中任何一条是红色，这条边的2个端点和P相连的2边便组成1个红色三角形。若这3条边中任何一条都不是红色，它们必然是蓝色，因此，它们组成了1个蓝色三角形。而在K5内，不一定有1个红色的三角形或蓝色的三角形。每个端点和毗邻的2个端点的线是红色，和其余2个端点的连线是蓝色就可以。这个定理的通俗版本就是友谊定理。

拉姆齐二染色定理_拉姆齐二染色定理 -破解

拉姆齐二染色定理被大三学生刘嘉忆破解

2011年5月，由北京大学等联合举办的逻辑学术会议上，还是大三的刘嘉忆报告了他对反推数学中的拉姆齐（Ramsly）二染色定理的证明论强度的研究。这是由英国数理逻辑学家Seetapun于二十个世纪90年代提出的1个猜想，十多年来，许多著名研究者一直努力都没有解决。
刘嘉忆的报告给这一悬而未决的公开问题1个否定式的回答，彻底解决了Seetapun的猜想。

本文标题：拉姆齐二染色定理-拉姆齐定理：拉姆齐定理-名称，拉姆齐定理-简介
本文地址： http://www.61k.com/1079914.html