找回密码
 欢迎注册
查看: 30904|回复: 21

[分享] 拉姆塞(Ramsay)理论

[复制链接]
发表于 2008-4-5 20:00:12 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
  拉姆塞是位天才的英国科学家,只活了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理论是图论四大难题之一
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-6 09:43:14 | 显示全部楼层
感觉图论、组合数学等比较考验人的构造思维,
其产生的结论往往很神秘,甚至看似不合理,但终却逃不出其手心,非常奥妙。
我没有经过这方面的专业教育,不敢多言了。。。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-25 09:00:34 | 显示全部楼层
原帖由 kenmark 于 2008-4-5 20:00 发表 Ramsay理论是图论四大难题之一

lz可否介绍一下是哪四大难题么,俺研究了半天图论居然没听说过这个
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-25 09:06:04 | 显示全部楼层
哈密尔顿算不算四大?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-25 09:26:56 | 显示全部楼层
拉姆塞,看到这个名字,我首先想到的是惰性气体的发现者,查阅查阅了一下拉姆塞的生平,终发现此 拉姆塞 非 彼拉姆塞 也。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-25 09:31:46 | 显示全部楼层
我觉得翻译为拉姆齐的比较多
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-25 10:37:57 | 显示全部楼层
据说有一个说法:
魔鬼对人类说:我给你们一年的时间,告诉我r(5,5)是多少,否则我毁灭人类。于是,人类停下了别的工作,集中了所有的数学家、工程师和计算机,开始计算r(5,5)。
如果魔鬼当时要求的是r(6,6)的值,那么,人类会怎么做呢?人类会停下别的工作,集中所求的力量研究武器和魔法,准备去和魔鬼决战。

评分

参与人数 1鲜花 +1 收起 理由
mathe + 1 精品文章

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-25 19:27:52 | 显示全部楼层
赞一个楼上,r(6,6)的确太可怕了~
哈密尔顿好像是四大,以前某人和我说的,有点忘了。。~
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-4-25 19:36:59 | 显示全部楼层
R(x,y)23456 7
2234567
369141823
418284466
55594156
6178322
7

上表乃从 《组合数学及其算法》 得到


http://en.wikipedia.org/wiki/Ramsey's_theorem 似乎和上面的不一致
r,s12345678910
11111111111
212345678910
31369141823283640–43
4149182535–4149–6156–8473–11592–149
515142543–4958–8780–143101–216125–316143–442
6161835–4158–87102–165113–298127–495169–780179–1171
7172349–6180–143113–298205–540216–1031233–1713289–2826
8182856–84101–216127–495216–1031282–1870317–3583≤ 6090
9193673–115125–316169–780233–1713317–3583565–6588580–12677
1011040–4392–149143–442179–1171289–2826≤ 6090580–12677798–23556
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-4-26 20:15:17 | 显示全部楼层
呵呵,老实说我更信维基的~不过好久没看,上下界居然好了那么多,呵呵,孤陋了~
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-29 08:27 , Processed in 0.058795 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表