拉姆齐定理(维基百科).doc

拉姆齐定理
维基百科,自由的百科全书
在组合数学上, 拉姆齐(Ramsey)定理是要解决以下的问题:要找这样一个最小的数n ,使得n个人中必定有k个人相识或l个人互不相识。
这个定理以弗兰克·普伦普顿·拉姆齐命名, 1930年他在论文On a Problem in Formal Logic (《形式逻辑上的一个问题》)证明了R(3,3)=6。
目录 
 [隐藏] 
1 拉姆齐数的定义
2 拉姆齐数的数值或上下界
3 R(3,3)等于6的证明
4 外部链接
[ 编辑 ]拉姆齐数的定义
拉姆齐数 ,用图论的语言有两种描述:
对于所有的N顶图,包含k个顶的团或l个顶的独立集。 具有这样性质的最小自然数N就称为一个拉姆齐数,记作R( k , l );
在着色理论中是这样描述的:对于完全图 K n的任意一个2 边着色 ( e 1 , e 2 ) ,使得K n [ e 1 ]中含有一个k阶子完全图, K n [ e 2 ]含有一个l阶子完全图,则称满足这个条件的最小的n为一个拉姆齐数。 (注意: K i按照图论的记法表示i阶完全图)
拉姆齐证明,对与给定的正整数数k及l ,R( k , l )的答案是唯一和有限的。
拉姆齐数亦可推广到多于两个数:
对于完全图 K n的每条边都任意涂上r种颜色之一,分别记为e 1 , e 2 , e 3 ,..., e r ,在K n中,必定有个颜色为e 1的l 1阶子完全图,或有个颜色为e 2的l 2阶子完全图……或有个颜色为e r的l r阶子完全图。 符合条件又最少的数n则记为R( l 1 , l 2 , l 3 ,..., l r ; r )。
[ 编辑 ]拉姆齐数的数值或上下界
已知的拉姆齐数非常少, 保罗·艾狄胥曾以一个故事来描述寻找拉姆齐数的难度:「想像有队外星人军队在地球降落,要求取得R(5,5)的值,否则便会毁灭地球。在这个情况,我们应该集中所有电脑和数学家尝试去找这个数值。若它们要求的是R(6,6)的值,我们要尝试毁灭这班外星人了。」
显然易见的公式: R(1, s )=1, R(2, s )= s , R( l 1 , l 2 , l 3 ,..., l r ; r )=R( l 2 , l 1 , l 3 ,..., l r ; r )=R( l 3 , l 1 , l 2 ,..., l r ; r)(将l i的顺序改变并不改变拉姆齐的数值)。
r , s
3
4
5
6
7
8
9
10
3
6
9
14
18
23
28
36
40 – 43
4
9
18
25
35 – 41
49 – 61
56 – 84
73 – 115
92 – 149
5
14
25
43 – 49
58 – 87
80 – 143
101 – 216
125 – 316
143 – 442
6
18
35 – 41
58 – 87
102 – 165
113 – 298
127 – 495
169 – 780
179 – 1171
7
23
49 – 61
80 – 143
113 – 298
205 – 540
216 – 1031
233 – 1713
289 – 2826