人生倒计时
- 今日已经过去小时
- 这周已经过去天
- 本月已经过去天
- 今年已经过去个月
什么是西塔潘猜想
西塔潘猜想是对拉姆齐二染色定理的证明强度研究的一个猜想。拉姆齐二染色定理是以数学家弗兰克·普伦普顿·拉姆齐命名。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)的答案是唯一和有限的。
西塔潘猜想是什么?
西塔潘猜想又称“拉姆齐二染色定理”,是由英国数理逻辑学家西塔潘于上个世纪90年代提出的一个猜想。在组合数学上,拉姆齐(ramsey)定理是要解决以下的问题:要找这样一个最小的数n,使得n个人中必定有k个人相识或l个人互不相识。
西塔潘猜想的证明
R(3,3)等于6的证明
证明:在一个K6的完全图内,每边涂上红或蓝色,必然有一个红色的三角形或蓝色的三角形。任意选取一个端点P,它有5条边和其他端点相连。根据鸽巢原理,3条边的颜色至少有两条相同,不失一般性设这种颜色是红色。在这3条边除了P以外的3个端点,它们互相连结的边有3条。若这3条边中任何一条是红色,这条边的两个端点和P相连的2边便组成一个红色三角形。若这3条边中任何一条都不是红色,它们必然是蓝色,因此,它们组成了一个蓝色三角形。而在K5内,不一定有一个红色的三角形或蓝色的三角形。每个端点和毗邻的两个端点 的线是红色,和其余两个端点的连线是蓝色即可。这个定理的通俗版本就是友谊定理。
西塔潘猜想既然被证明了,那结论是什么?
结论是:在组合数学上,拉姆齐定理是要解决以下的问题,要找这样一个最小的数n,使得n个人中必定有k个人相识或l个人互不相识。
2011年5月,由北京大学、南京大学和浙江师范大学联合举办的逻辑学术会议在浙江师范大学举行,中南大学数学科学与计算技术学院酷爱数理逻辑的刘嘉忆的报告给这一悬而未决的公开问题一个否定式的回答,并彻底解决了西塔潘的猜想。
西塔潘猜想是由英国数理逻辑学家西塔潘于上个世纪90年代提出的一个反推数学领域关于拉姆齐二染色定理证明强度的猜想。
扩展资料:
“拉姆齐二染色定理”以弗兰克·普伦普顿·拉姆齐命名,拉姆齐数的定义拉姆齐数,用图论的语言有两种描述:对于所有的N顶图,包含k个顶的团或l个顶的独立集。
具有这样性质的最小自然数N就称为一个拉姆齐数,记作R(k,l),在着色理论里是这样描述的,对于完全图Kn的任意一个2边着色(e1,e2),要Kn[e1]中含有一个k阶子完全图,Kn[e2]含有一个l阶子完全图,则称满足这个条件的最小的n为一个拉姆齐数。
拉姆齐证明,对与给定的正整数k及l,R(k,l)的答案是唯一与有限的。