许成章，梁文忠

(1.2.梧州学院，广西 梧州 543002）

对角Ram sey数R（22，23）的新下界

许成章1，梁文忠2

(1.2.梧州学院，广西 梧州 543002）

研究Ramsey数下界的问题，发现了Paley图的一个新的自同构，形成计算Paley图团数的一个新方法，为解决Radziszowski问题提供一个新思路，获得阶段性成果：计算出14813阶Paley图的团数，得到一个对角Ramsey数的新下界：R（23，23）≥29629。

Ramsey数；下界；Paley图；团数；自同构

1 引言

英国数学家F.P.Ramsey[1]在1928年证明了一个定理，后世学者称之为Ramsey定理，相关函数称为Ramsey数，于是确定Ramsey数就成为组合数学中非常困难的问题[2-4]。对于任意给定的整数n≥3，所谓对角Ramsey数R（n,n） 是指满足如下性质的最小正整数r：用两种颜色把r阶完全图Kr的边任意染色后，在Kr中一定有单色的Kr。

人们对Ramsey数R（n,n） 所知甚少。数十年来，各国学者努力探索Ramsey数的上界和下界，试图逐步逼近Ramsey数的准确值.这是涉及到巨量运算的非常困难的一个NP-C问题，任何理论和方法上的创新以及所获得的新成果，都能使人们对Ramsey数加深认识而引起学术界的关注。

关于研究Ramsey数的困难程度，匈牙利数学家Erdǒs说：“需要过上百万年，人们才会得到一些认识，甚至那时也不能达到完全的认识”[3]147。曾任美国数学会主席的Graham猜测人们至少在100年内发现不了 的准确值[3]146。我国数学家李乔说Ramsey数研究的“这个问题是对人类智慧的真正挑战”[3]17。

1947年匈牙利数学家Erdǒs[5]首创概率方法得到对角Ramsey数下界的渐近估计.1955年美国数学家Greenwood和Gleason[6]首创构造性方法，得到历史上第一批Ramsey数的准确值，其中两个对角Ramsey数是这样得到的：首先利用Paley图计算出R（3,3）＞5 和 R（4,4）＞17，再用存在性的方法证明 R（3,3）≤6 和 R（4,4）≤18，就得到 R（3,3）=6 和 R（4,4）=18。……