一個對角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）