一個對角Ram sey數(shù)的新下界

梁文忠，許成章

（1.2.梧州學(xué)院，廣西梧州543002）

一個對角Ram sey數(shù)的新下界

梁文忠1，許成章2

（1.2.梧州學(xué)院，廣西梧州543002）

該文研究了對角Ramsey數(shù)的下界問題。利用Paley圖的二級自同構(gòu)，提高運算效率，計算出16993階的Paley圖的團數(shù)，獲得一個對角Ramsey數(shù)的新下界：R（22，22）≥33989。

Ramsey數(shù)；下界；Paley圖；團數(shù)；自同構(gòu)

1 引言

確定Ramsey數(shù)是組合數(shù)學(xué)中非常著名的困難問題[1-3]。最先引起學(xué)術(shù)界重視的，是對角Ramsey數(shù)R（n,n）的下界。任意給定整數(shù)n≥3，所謂對角Ramsey數(shù)R（n,n）是指滿足如下性質(zhì)的最小正整數(shù)r：用兩種顏色把r階完全圖Kr的邊任意染色后，在Kr中一定有單色的Kn。

1947年，匈牙利數(shù)學(xué)家Erdos首創(chuàng)概率方法[4－5]，得到漸近估計式R（n,n）≥（1－0（1））2(n-1)/2n/e.后世學(xué)者沿用這種方法也獲得了一些卓越成果。

1955年，美國數(shù)學(xué)家Greenwood和Gleason[6]首創(chuàng)構(gòu)造性方法，得到歷史上第一批Ramsey數(shù)的準(zhǔn)確值，其中兩個對角Ramsey數(shù)R（3,3）=6和R（4,4）=18就涉及到5階與17階Paley圖的團數(shù)。

上世紀(jì)下半葉，研究經(jīng)典Ramsey數(shù)是學(xué)術(shù)界的熱門課題。1993年，美國數(shù)學(xué)家Radziszowski首次發(fā)表動態(tài)綜述論文《Small Ramsey Numbers》[7]，以后經(jīng)常修改更新，及時報道當(dāng)前各項Ramsey數(shù)的最佳成果，以及相關(guān)的大量參考文獻(xiàn)，是當(dāng)今學(xué)術(shù)界研究Ramsey數(shù)的重要參照依據(jù)。

Paley圖是用4K＋1型素數(shù)的二次剩余構(gòu)造的循環(huán)圖，由其團數(shù)可以推導(dǎo)出對角Ramsey數(shù)的下界，因此學(xué)術(shù)界非常重視計算Paley圖的團數(shù)。例如，Kalbfleisch[8]、Burling and Reyner[9]、Shearer[10]、Mathon[11]等學(xué)者憑借速度越來越快的計算機分別計算出37、101、109、281、373、797、1277、1493、2741、2801、4457階Paley圖的團數(shù)。隨著Paley圖階數(shù)的增大，Paley圖中同構(gòu)子圖的數(shù)量呈指數(shù)型增長，計算其團數(shù)就要反復(fù)計算越來越多的同構(gòu)子圖，所遇到的巨量運算使計算機耗時急劇上升，因此僅僅依靠計算機的升級換代就越來越難取得新成果了。

為了克服上述困難，羅海鵬與蘇文龍在論文[12]和論文[13]中首次發(fā)現(xiàn)了Paley圖自同構(gòu)，用一般電腦計算得階數(shù)為5501與8941階Paley圖的團數(shù)，引起學(xué)術(shù)界關(guān)注。此后，IBM公司的計算機科學(xué)家Shearer根據(jù)論文[12]和論文[13]的理論用高速電腦計算Paley圖的團數(shù)，在計算到接近10000階的Paley圖就耗時極多而非常困難了。長期跟蹤該領(lǐng)域研究進展的美國數(shù)學(xué)家Radziszowski期盼學(xué)術(shù)界有所創(chuàng)新，提出問題（簡稱Rad.問題）：計算20000階以內(nèi)的Paley圖的團數(shù)（見http://www.cs.rit.edu/～spr/topics. html）。

由于論文論文[12]和論文[13]的理論識別同構(gòu)子圖的能力不夠強，運算效率不太高，因此要解決上述Rad.問題，僅靠現(xiàn)有理論和計算機的升級換代是遠(yuǎn)遠(yuǎn)不夠的。我們在論文[14]指出：必須深入研究Paley圖的結(jié)構(gòu)性質(zhì)，特別是其深層次自同構(gòu)，以及它的顯性作用、隱性作用和加速效應(yīng)，完善識別同構(gòu)子圖的理論和方法，減少大量同構(gòu)子圖的重復(fù)計算，提高運算效率。此后，我們的論文[15]和論文[16]利用Paley圖的二級自同構(gòu)理論，計算出9533、13537、14969階Paley圖的團數(shù)，得到對角Ramsey數(shù)的新下界：R（20,20）≥19069，R（21,21）≥27077，R（22,22）≥29941。

現(xiàn)在，我們在發(fā)現(xiàn)Paley圖的深層次自同構(gòu)、揭示其隱性作用和加速效應(yīng)、完善識別同構(gòu)子圖的理論和方法等各個方面的工作都有新的進展，參照論文[16]的算法，我們計算出16993階Paley圖的團數(shù)為21，其中一個最大團是

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

注意到

引理1[7]設(shè)p階Paley圖的團數(shù)為c，則有R（c+1，c+1）≥2p+3.

我們就得到一個對角Ramsey數(shù)的新下界：

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

我們研究的Paley圖深層次自同構(gòu)理論獲得了較大進展。實踐表明，這種理論能夠識別同構(gòu)子圖，減少大量同構(gòu)子圖的反復(fù)計算，在很大程度上遏制運算量急劇增長的勢頭。因此，我們預(yù)計將在不太長的時間內(nèi)解決Rad.問題，獲得更多更好的對角Ramsey數(shù)新下界，推動Ramsey數(shù)的研究進展。

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

[2]李喬.拉姆塞理論[M].大連:大連理工大學(xué)出版社，2011.

[3]李喬.組合數(shù)學(xué)基礎(chǔ)[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]蘇文龍,羅海鵬,李喬.多色經(jīng)典Ramsey數(shù)的下界[J].中國科學(xué)(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問題復(fù)雜程度的一個模型——對計算Paley圖團數(shù)的探索實踐作出預(yù)測[J].湘潭大學(xué)自然科學(xué)學(xué)報, 2011(4)：7～11.

[15]許成章,等.用Paley圖計算對角Ramsey數(shù)下界的新方法[J].數(shù)學(xué)雜志，2012(3):547-555.

[16]梁文忠,等.用Paley圖的二級自同構(gòu)計算Ramsey數(shù)下界[J].內(nèi)蒙古師范大學(xué)學(xué)報:自然科學(xué)版,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－），男，廣西賀州人，梧州學(xué)院副教授，研究方向：計算機算法、組合優(yōu)化。

許成章（1976－），男，廣西蒼梧人，梧州學(xué)院講師，主要研究方向：組合數(shù)學(xué)、圖論和高職數(shù)學(xué)教學(xué)改革。

（責(zé)任編輯：高堅）

2013-06-23

廣西自然科學(xué)基金資助項目（0991278）