一个对角Ram sey数的新下界

梁文忠，许成章

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

一个对角Ram sey数的新下界

梁文忠1，许成章2

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

该文研究了对角Ramsey数的下界问题。利用Paley图的二级自同构，提高运算效率，计算出16993阶的Paley图的团数，获得一个对角Ramsey数的新下界：R（22，22）≥33989。

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

1 引言

确定Ramsey数是组合数学中非常著名的困难问题[1-3]。最先引起学术界重视的，是对角Ramsey数R（n,n）的下界。任意给定整数n≥3，所谓对角Ramsey数R（n,n）是指满足如下性质的最小正整数r：用两种颜色把r阶完全图Kr的边任意染色后，在Kr中一定有单色的Kn。

1947年，匈牙利数学家Erdos首创概率方法[4－5]，得到渐近估计式R（n,n）≥（1－0（1））2(n-1)/2n/e.后世学者沿用这种方法也获得了一些卓越成果。

1955年，美国数学家Greenwood和Gleason[6]首创构造性方法，得到历史上第一批Ramsey数的准确值，其中两个对角Ramsey数R（3,3）=6和R（4,4）=18就涉及到5阶与17阶Paley图的团数。

上世纪下半叶，研究经典Ramsey数是学术界的热门课题。1993年，美国数学家Radziszowski首次发表动态综述论文《Small Ramsey Numbers》[7]，以后经常修改更新，及时报道当前各项Ramsey数的最佳成果，以及相关的大量参考文献，是当今学术界研究Ramsey数的重要参照依据。

Paley图是用4K＋1型素数的二次剩余构造的循环图，由其团数可以推导出对角Ramsey数的下界，因此学术界非常重视计算Paley图的团数。例如，Kalbfleisch[8]、Burling and Reyner[9]、Shearer[10]、Mathon[11]等学者凭借速度越来越快的计算机分别计算出37、101、109、281、373、797、1277、1493、2741、2801、4457阶Paley图的团数。随着Paley图阶数的增大，Paley图中同构子图的数量呈指数型增长，计算其团数就要反复计算越来越多的同构子图，所遇到的巨量运算使计算机耗时急剧上升，因此仅仅依靠计算机的升级换代就越来越难取得新成果了。

为了克服上述困难，罗海鹏与苏文龙在论文[12]和论文[13]中首次发现了Paley图自同构，用一般电脑计算得阶数为5501与8941阶Paley图的团数，引起学术界关注。此后，IBM公司的计算机科学家Shearer根据论文[12]和论文[13]的理论用高速电脑计算Paley图的团数，在计算到接近10000阶的Paley图就耗时极多而非常困难了。长期跟踪该领域研究进展的美国数学家Radziszowski期盼学术界有所创新，提出问题（简称Rad.问题）：计算20000阶以内的Paley图的团数（见http://www.cs.rit.edu/～spr/topics. html）。

由于论文论文[12]和论文[13]的理论识别同构子图的能力不够强，运算效率不太高，因此要解决上述Rad.问题，仅靠现有理论和计算机的升级换代是远远不够的。我们在论文[14]指出：必须深入研究Paley图的结构性质，特别是其深层次自同构，以及它的显性作用、隐性作用和加速效应，完善识别同构子图的理论和方法，减少大量同构子图的重复计算，提高运算效率。此后，我们的论文[15]和论文[16]利用Paley图的二级自同构理论，计算出9533、13537、14969阶Paley图的团数，得到对角Ramsey数的新下界：R（20,20）≥19069，R（21,21）≥27077，R（22,22）≥29941。

现在，我们在发现Paley图的深层次自同构、揭示其隐性作用和加速效应、完善识别同构子图的理论和方法等各个方面的工作都有新的进展，参照论文[16]的算法，我们计算出16993阶Paley图的团数为21，其中一个最大团是

{0，1，292，869，3302，3894，4763，9899，10950，10981，11025，11503，12027，12906，13623，14681，14820，15613，15213，15822，16732}.

注意到

引理1[7]设p阶Paley图的团数为c，则有R（c+1，c+1）≥2p+3.

我们就得到一个对角Ramsey数的新下界：

定理1 R（22,22）≥33989.

我们研究的Paley图深层次自同构理论获得了较大进展。实践表明，这种理论能够识别同构子图，减少大量同构子图的反复计算，在很大程度上遏制运算量急剧增长的势头。因此，我们预计将在不太长的时间内解决Rad.问题，获得更多更好的对角Ramsey数新下界，推动Ramsey数的研究进展。

[1]R.L.Graham,B.L.Rothschild,and J.H.Spencer.Ramsey theory[M].JohnWiley&Sons,1990.

[2]李乔.拉姆塞理论[M].大连:大连理工大学出版社，2011.

[3]李乔.组合数学基础[M].北京：高等教育出版社，1993.

[4]P.Erdos.Some remarkson the theoryofgraphs[J].Bulletin of the American MathematicalSociety,1947,53:292～294.

[5]P.Erdos.Graph theory and probability[J].Canadian JournalofMathematics,1959,11:34～38.

[6]R.E.Greenwood and A.M.Gleason.Combinatorial relationsand chromatic graphs[J].Canadian JournalofMathematics,1955,7:1～7.

[7]S.P.Radziszowski.SmallRamsey Numbers[J].The Electronic JournalofCombinatorics,View the Journal,Dynamic Surveys,2011,August22 ElJC revision#13,(2011),DS1.13:1～84（http://www.combinatorics.org）or（http://www.cs.rit.edu/～spr/ElJC/ejcram13.pdf）

[8]J.G.Kalbfleisch.Construction ofSpecialEdge-Chromatic Graphs[J].Canadian Mathematical Bulletin,8(1965)575～584.

[9]J.P.Burling and S.W.Reyner.Some Lower Boundsof the Ramsey Numbers n(k,k)[J].JournalofCombinatorial Theory,Series B,13 (1972)168～169.

[10]J.B.Shearer.Lower Bounds for SmallDiagonalRamsey Numbers[J].JournalofCombinatorial Theory,SeriesA,42(1986)302～304.

[11]R.Mathon.Lower Bounds for Ramsey Numbers and Association Schemes[J].Journal of Combinatorial，Theory,Series B,42(1987) 122-127.

[12]苏文龙,罗海鹏,李乔.多色经典Ramsey数的下界[J].中国科学(A辑),1999,29(5):408-413.

[13]Luo Haipeng,SuWenlongand LiZhengchong.The propertiesofself-complementary graphsand new lowerbounds for diagonalRamsey numbers[J].Australasian JournalofCombinatorics,2002,25:103-116.

[14]陈红,等.刻画NP-C问题复杂程度的一个模型——对计算Paley图团数的探索实践作出预测[J].湘潭大学自然科学学报, 2011(4)：7～11.

[15]许成章,等.用Paley图计算对角Ramsey数下界的新方法[J].数学杂志，2012(3):547-555.

[16]梁文忠,等.用Paley图的二级自同构计算Ramsey数下界[J].内蒙古师范大学学报:自然科学版,2012(6):591-596.

A New Lower Bound of a Diagonal Ram sey Number

Liang Wenzhong1,Xu Chengzhang2
(W uzhou University,W uzhou 543002,China)

This papermakes an analysis of the lower bound of a diagonal Ramsey number by applying the 2nd automorphism of Paley pattern,computing efficiency being improved.The cluster number of Paley pattern of the exponent of 16993 is worked out and a new lower bound of a diagonal Ramsey is obtained:R（22，22）≥33989.

Ramsey number;the lower bound;Paley pattern;cluster number;automorphism

O157.5

A

1673-8535(2013)06-0040-03

梁文忠（1963－），男，广西贺州人，梧州学院副教授，研究方向：计算机算法、组合优化。

许成章（1976－），男，广西苍梧人，梧州学院讲师，主要研究方向：组合数学、图论和高职数学教学改革。

（责任编辑：高坚）

2013-06-23

广西自然科学基金资助项目（0991278）