关于Ｒａｍｓｅｙ　数的等式Ｒ（ｐ＋１，ｐ＋１）＝Ｒ（ｐ，ｐ＋３）（ｐ≥３）

【摘要】 本文进一步阐述了约束共存性概念，从而得到；（Kq｜K-q）=R（p，q）=r（p-1，q），（q≥p≥2）这里, 报道我们获得的最新关于Ramsey数的成果, 如R（p，q-1）≥r（p-1，Q+1）（q-1>p>2）R(p+1,p+1)=R(p,p+3)(p≥3)并利用已知的界，终于确定两个Ramsey数：R(5,5) = 49,R(4,7) = 49. 对于多色情形，我们可得到R(p,p,p=R(p-1,p+1,p+1)-1(p≥3)。

【关键词】 Ramsey现象；Ramsey数； 约束共存极小性；约束不可免性

【中图分类号】：G623.5【文献标识码】：A 【文章编号】：1009-9646(2008)05-0170-01

上世纪二十年代末，一位英国逻辑学家Frank Ramsey建立了如下著名的理论^[1-4]：

Ramsey定理. 对于任意给定的正整数p,q≥2，存在一个正整数n，使得对n元集合的所有n(n-1)/2个2元集任意划分为两个集合：X 、Y，则不可避免发生：或者X含有p个元素的所有2元集,或者,Y含有q个元素的所有2元集。 则称正整数n具有参数p,q-Ramsey性质。这样的最小整数n称为Ramsey数，记为R(p,q)。

至今人们仅知道很少的几个Ramsey数的准确值^[3-5]。到目前为止，关于Ramsey数的许多基本问题还很不清楚，如对已知的Ramsey数甚至还不能从理论上解释清楚为什么R(4，4)=R(3,6)?=R(2,4,4)-1=17?等等。

本文即从Ramsey数的定义着手，以“约束共存”思想，提出了另一个等价的Ramsey数定义。由这个定义，可以得到一系列基本性质和大小关系。

2 约束共存性与Ramsey数

首先，我们引入2色约束共存的概念，然后，再将其推广到多色及超图情形。

定义1. 设q,p≥2整数,若存在有限整数n，在不出现红色的约束下, 无论对完全图Kn的边怎样2着色(红或蓝)，Kn中不可避免地出现蓝色Kq但蓝色Kq+1可不出现，那么，我们称n具有在无一色Kp约束下另一色Kq不可免性。

显然，这样的整数n是存在的。记为n（Kq｜K-q）， 这样的最小整数记为L（Kq｜K-q）, 这样的最大整数记为B（Kq｜K-q）。

例1. 根据这个定义，我们可验证：

L（K2｜K-2）=B（K2｜K-2）,L（Kn｜K-2）=B（Kn｜K-2）=L（K2｜K-n）=n(n∈N)，

B（K2｜K-3）=5，B（K2｜K-4）=8，L（K3｜K-3）=6，L（K4｜K-3）=L（K3｜K-4）=9，…

定义2.设q，p≥2为整数, 若存在有限整数n，使得对n阶完全图Kn的所有边用红、蓝两色着色，每边着一色，在Kn中既不出现红Kp又不出现蓝Kq的约束下，无论怎么着色，红色Kp-1和蓝色Kq-1都总是共同存在于Kn，则称n具有参数p-1，q-1的约束共存性质。最小的这样的整数n则记为r（p-1，q-1）^[6]。

例2. r(1,1)=1; r(1,5)=5，r(2,3)=6，

引理.假设q，p≥2为整数，则R（p，q）-1具有参数p-1，q-1的约束共存性质的最大整数。这个数记为Sarc（p-1，q-1），(参看[6])

我们称在此约束下的2色完全图 为参数 约束共存饱和态或极大态。不难知道， 也存在。 称在此约束下2色完全图 为参数 约束共存初始态或极小态。

例3. R(3,4)-1=Sarc(2,3)=8.

现在我们给出关于约束不可免性与约束共存性之间的关系以及约束共存极小态和相应的Ramsey现象之间的对应关系。下面的若干定理揭示了这一系列事实(证明略去)。

定理1. 设q≥p≥2为整数，则下列等式成立

例4.r(2,5)=R(3,5).

推论1. 设q≥p≥2为整数，则正整数n具有参数p-1，q约束共存性质的充分必要条件是边2色完全图Kn在不出现红色完全子图Kp和蓝色完全子图Kq+1限制下，必然出现蓝色完全子图Kq。

定理2.B（Kq｜K-p）〈L（Kq-1｜K-p+1）（q-1〉p≥2）

定理3.L（Kp+3｜K-p）=L（Kp+1｜K-p+1）=（p≥3）

例5. 利用上述性质和已知的上下界^{[5, 6]}，我们容易确定：R(5,5)=R(4,7)=49.

最后指出，对于多色及超图情形而言，也有相应的约束不可免性、约束共存性(参看^[6])。同样地，上述各相应的定理也成立。

参考文献

[1] Richard A.Brualdi,Introductory Combinatorics(Fifth Edition)[M],Prentice-Hell,2004

[2] 卢开澄，卢华明，组合数学（第三版）[M]，北京：清华大学出版社，2002

[3] 杨骅飞，王朝瑞，组合数学及其应用[M]，北京：北京理工大学出版社，1992

[4] 张先迪，李正良，图论及其应用[M]，北京：高等教育出版社，2005

[5] Radziszowski, S. P.,Small Ramsey Numbers[J], Electronic J.Combinatorics, Dynamical Survey DS1,2006..cn/qkpdf/gxjy/gxjy200805/gxjy200805118.pdf" style="color:red" target="_blank">原版全文

推荐访问:等式 Ramsey