2022年8月10日

  拉姆塞(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)的一个上界:

发表评论

您的电子邮箱地址不会被公开。