西塔潘猜想，有兴趣研究下

mathzhongguo

[这个贴子最后由mathzhongguo在 2011/10/18 05:58pm 第 2 次编辑]

西塔潘猜想
   又称“拉姆齐二染色定理”，是由英国数理逻辑学家西塔潘于上个世纪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)的值，我们要尝试毁灭这班外星人了。

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

仍未解决的问题
已知　R(3,3)=6和R(4,4)=8 ， 但　R(5,5)却不知道是多少,只知道范围 43《R(5,5)《49和102《R(6,6)《165。
详细点的解释在http://en.wikipedia.org/wiki/Ramsey%27s_theorem西塔潘猜想

moranhuishou

要证明一个命题，首先是理解命题，只有彻底的理解了，才有可能证明，一知半解是不行的。
现在是，看了两遍都木看懂——笨哪，所以就先不证明了，哈哈。

常量

R(4,4)=18

常量

组合学精美的定理
完全的无序是不可能的
数论的三颗明珠
陶哲轩“存在任意长的素数等差数列”