拉姆塞（Ramsay）理论

kenmark

　　拉姆塞是位天才的英国科学家，只活了26岁。在他去世的1930年，他发表了一篇学术论文，其副产物就是所谓拉姆塞理论。 　　拉姆塞理论可以用通常的语言来表述。在一个集会上，两个人或者彼此认识，或者彼此不认识，拉姆塞得出结果是说，当集会人数大于或等于6时，则必定有3个人，他们或者彼此者认识或者彼此都不认识。6称为拉姆塞数，记r(3,3)。进一步当集会人数大于或等于18时，则必定有4个人，他们或者彼此都认识或者彼此都不认识，用记号表示就是r(4,4)=18。可是集会有多少人，才能有5个人都彼此认识或都不认识呢？至今为此，r(5,5)的精确数目我们还不知道，至于其他的r(n,n)当然就更不清楚了。不过，我们的确证明r(n,n)是一个有限数，的确存在，甚至有精确的上界和下界。只是其中究竟哪一个是拉姆塞数，就不得而知了。因此，求r(n,n)的精确值是我们的头一个难题。 　　拉姆塞理论还有进一步的推广，一个最简单的推广是r(s,t)，也就是集会至少有多少人，才能有s个人互相都认识或者t个人互相都不认识。可以证明r(s,t)=r(t,s)，因此，我们不妨假定s≤t。现在知道的精确的r(s,t)的值极少，只有如下的9种情形:r(3,3)=6 r(3,4)=9 r(3,5)=14 r(3,6)=18 r(3,7)=23 r(3,8)=28 r(3,9)=36 r(4,4)=18 r(4,5)=25 而且我们还知道r(3,t)的一个上界：$r(3,t) \le \frac{t^2+3}{2}$ Ramsay理论是图论四大难题之一

gxqcn

感觉图论、组合数学等比较考验人的构造思维， 其产生的结论往往很神秘，甚至看似不合理，但终却逃不出其手心，非常奥妙。 我没有经过这方面的专业教育，不敢多言了。。。

shshsh_0510

原帖由 kenmark 于 2008-4-5 20:00 发表 Ramsay理论是图论四大难题之一

lz可否介绍一下是哪四大难题么，俺研究了半天图论居然没听说过这个

无心人

哈密尔顿算不算四大？

liangbch

拉姆塞,看到这个名字，我首先想到的是惰性气体的发现者，查阅查阅了一下拉姆塞的生平，终发现此 拉姆塞 非 彼拉姆塞 也。

shshsh_0510

我觉得翻译为拉姆齐的比较多

zgg___

据说有一个说法： 魔鬼对人类说：我给你们一年的时间，告诉我r(5,5)是多少，否则我毁灭人类。于是，人类停下了别的工作，集中了所有的数学家、工程师和计算机，开始计算r(5,5)。 如果魔鬼当时要求的是r(6,6)的值，那么，人类会怎么做呢？人类会停下别的工作，集中所求的力量研究武器和魔法，准备去和魔鬼决战。

kenmark

赞一个楼上，r(6,6)的确太可怕了～ 哈密尔顿好像是四大，以前某人和我说的，有点忘了。。～

无心人

R(x,y)	2	3	4	5	6	7
2	2	3	4	5	6	7
3		6	9	14	18	23
4			18	28	44	66
5				55	94	156
6					178	322
7

上表乃从 《组合数学及其算法》 得到 但 http://en.wikipedia.org/wiki/Ramsey's_theorem 似乎和上面的不一致

r,s	1	2	3	4	5	6	7	8	9	10
1	1	1	1	1	1	1	1	1	1	1
2	1	2	3	4	5	6	7	8	9	10
3	1	3	6	9	14	18	23	28	36	40–43
4	1	4	9	18	25	35–41	49–61	56–84	73–115	92–149
5	1	5	14	25	43–49	58–87	80–143	101–216	125–316	143–442
6	1	6	18	35–41	58–87	102–165	113–298	127–495	169–780	179–1171
7	1	7	23	49–61	80–143	113–298	205–540	216–1031	233–1713	289–2826
8	1	8	28	56–84	101–216	127–495	216–1031	282–1870	317–3583	≤ 6090
9	1	9	36	73–115	125–316	169–780	233–1713	317–3583	565–6588	580–12677
10	1	10	40–43	92–149	143–442	179–1171	289–2826	≤ 6090	580–12677	798–23556

kenmark

呵呵，老实说我更信维基的～不过好久没看，上下界居然好了那么多，呵呵，孤陋了～