拉姆塞（Ramsay）理论
拉姆塞是位天才的英国科学家，只活了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理论是图论四大难题之一 感觉图论、组合数学等比较考验人的构造思维，
其产生的结论往往很神秘，甚至看似不合理，但终却逃不出其手心，非常奥妙。
我没有经过这方面的专业教育，不敢多言了。。。 原帖由 kenmark 于 2008-4-5 20:00 发表 Ramsay理论是图论四大难题之一
lz可否介绍一下是哪四大难题么，俺研究了半天图论居然没听说过这个:*-^ 哈密尔顿算不算四大？ 拉姆塞,看到这个名字，我首先想到的是惰性气体的发现者，查阅查阅了一下拉姆塞的生平，终发现此 拉姆塞 非 彼拉姆塞 也。 我觉得翻译为拉姆齐的比较多 据说有一个说法：
魔鬼对人类说：我给你们一年的时间，告诉我r(5,5)是多少，否则我毁灭人类。于是，人类停下了别的工作，集中了所有的数学家、工程师和计算机，开始计算r(5,5)。
如果魔鬼当时要求的是r(6,6)的值，那么，人类会怎么做呢？人类会停下别的工作，集中所求的力量研究武器和魔法，准备去和魔鬼决战。 赞一个楼上，r(6,6)的确太可怕了～
哈密尔顿好像是四大，以前某人和我说的，有点忘了。。～ R(x,y)23456 722345673691418234182844665559415661783227
上表乃从 《组合数学及其算法》 得到
但
http://en.wikipedia.org/wiki/Ramsey's_theorem 似乎和上面的不一致
r,s123456789101111111111121234567891031369141823283640–434149182535–4149–6156–8473–11592–149515142543–4958–8780–143101–216125–316143–4426161835–4158–87102–165113–298127–495169–780179–11717172349–6180–143113–298205–540216–1031233–1713289–28268182856–84101–216127–495216–1031282–1870317–3583≤ 60909193673–115125–316169–780233–1713317–3583565–6588580–126771011040–4392–149143–442179–1171289–2826≤ 6090580–12677798–23556 呵呵，老实说我更信维基的～不过好久没看，上下界居然好了那么多，呵呵，孤陋了～