許成章，梁文忠

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

對角Ram sey數(shù)R（22，23）的新下界

許成章1，梁文忠2

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

研究Ramsey數(shù)下界的問題，發(fā)現(xiàn)了Paley圖的一個新的自同構(gòu)，形成計算Paley圖團(tuán)數(shù)的一個新方法，為解決Radziszowski問題提供一個新思路，獲得階段性成果：計算出14813階Paley圖的團(tuán)數(shù)，得到一個對角Ramsey數(shù)的新下界：R（23，23）≥29629。

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

1 引言

英國數(shù)學(xué)家F.P.Ramsey[1]在1928年證明了一個定理，后世學(xué)者稱之為Ramsey定理，相關(guān)函數(shù)稱為Ramsey數(shù)，于是確定Ramsey數(shù)就成為組合數(shù)學(xué)中非常困難的問題[2-4]。對于任意給定的整數(shù)n≥3，所謂對角Ramsey數(shù)R（n,n） 是指滿足如下性質(zhì)的最小正整數(shù)r：用兩種顏色把r階完全圖Kr的邊任意染色后，在Kr中一定有單色的Kr。

人們對Ramsey數(shù)R（n,n） 所知甚少。數(shù)十年來，各國學(xué)者努力探索Ramsey數(shù)的上界和下界，試圖逐步逼近Ramsey數(shù)的準(zhǔn)確值.這是涉及到巨量運算的非常困難的一個NP-C問題，任何理論和方法上的創(chuàng)新以及所獲得的新成果，都能使人們對Ramsey數(shù)加深認(rèn)識而引起學(xué)術(shù)界的關(guān)注。

關(guān)于研究Ramsey數(shù)的困難程度，匈牙利數(shù)學(xué)家Erdǒs說：“需要過上百萬年，人們才會得到一些認(rèn)識，甚至那時也不能達(dá)到完全的認(rèn)識”[3]147。曾任美國數(shù)學(xué)會主席的Graham猜測人們至少在100年內(nèi)發(fā)現(xiàn)不了 的準(zhǔn)確值[3]146。我國數(shù)學(xué)家李喬說Ramsey數(shù)研究的“這個問題是對人類智慧的真正挑戰(zhàn)”[3]17。

1947年匈牙利數(shù)學(xué)家Erdǒs[5]首創(chuàng)概率方法得到對角Ramsey數(shù)下界的漸近估計.1955年美國數(shù)學(xué)家Greenwood和Gleason[6]首創(chuàng)構(gòu)造性方法，得到歷史上第一批Ramsey數(shù)的準(zhǔn)確值，其中兩個對角Ramsey數(shù)是這樣得到的：首先利用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。

所謂Paley圖，是指用4k+1型素數(shù)的二次剩余構(gòu)造的循環(huán)圖。美國學(xué)者Radziszowski的動態(tài)綜述論文[7]記錄了幾十年來學(xué)術(shù)界計算Paley圖的團(tuán)數(shù)和研究對角Ramsey數(shù)的非常緩慢的進(jìn)程：直到2002年，羅海鵬、蘇文龍等學(xué)者方才計算出4457、5501、8941階的Paley圖的團(tuán)數(shù)，得到 R(17，17)≥8917、R(18，18) ≥11005、R(19，19) ≥17885[8]。Radziszowski希望學(xué)術(shù)界有所創(chuàng)新，推動Ramsey數(shù)的研究進(jìn)展，在http://www.cs.rit.edu/～spr/topics.html中提出如下問題：

“計算20000階以內(nèi)的Paley圖的團(tuán)數(shù)”。

注意到，用通常的方法計算Paley圖的團(tuán)數(shù)，要反復(fù)計算大量同構(gòu)子圖，運算效率低下，因而這是非常困難的問題，迄今尚未見有文獻(xiàn)報道這個問題的研究進(jìn)展。筆者發(fā)現(xiàn)了Paley圖的一個新的自同構(gòu)，能夠減少大量同構(gòu)子圖的重復(fù)計算，改進(jìn)了計算對角Ramsey數(shù)的方法，用計算機探索得到一個尚未見有文獻(xiàn)報道的新成果。

2 Paley圖的二級導(dǎo)出子圖及其自同構(gòu)

設(shè)p≥29是4k+1型素數(shù)，Zp=｛-2K,…,-2,-1,0,1,2,…,2K｝是有限域，約定以下所有運算結(jié)果都在模P同余的意義下歸結(jié)到Zp。

定義1 設(shè)A是由模P的平方剩余形成的集。無向簡單圖Gp稱為Paley圖，其頂點集V(Gp)=Zp，邊集

引理 A[9]設(shè) B= ｛x｜x∈A，x-1∈A｝，Gp在 B上的導(dǎo)出子圖記為Gp[B]，則Gp[B]有如下六個自同構(gòu)：f0(x)=x，f1(x)=x-1，f2(x)=1-x-2，f3(x)=x(1-x)-1，f4(x)=x(1-x)-1，f5(x)=1-x，其中x∈B。

上述自同構(gòu)確定的等價關(guān)系“～”把B分拆成如下若干個等價類。其中代表元是α的等價類記為〈a〉各等價類代表元形成的集記為N 。

引理 B[8]｜B｜= （p-5）/4。設(shè) S=｜B｜mod 6，則有S=0，2，3，5四種情形。B1中的等價類一般都是如①所示的6元集，當(dāng)且僅當(dāng)S=0時B中的等價類都是6元集，當(dāng)且僅當(dāng) S=2或S=3時在B中有一個S元等價類，當(dāng)且僅當(dāng)S=5時在B中有一個2元等價類和一個3元等價類。

不妨把上述所說的導(dǎo)出子圖、自同構(gòu)和等價類分別稱為一級導(dǎo)出子圖、一級自同構(gòu)和一級等價類，本文在此基礎(chǔ)上引進(jìn)圖的二級導(dǎo)出子圖、二級自同構(gòu)、二級等價類等新概念。

定義 2 設(shè) B1=B=｛x｜x∈A,x-1∈A｝ ≠○，A a∈B1，令 B2= ｛x｜x∈B1,x-a∈A｝，稱a為B2的導(dǎo)出元，B2為a的導(dǎo)出集。

定理1 設(shè)a∈B1是B2的導(dǎo)出元，令

證明 易知f1作成Zp的一個置換。注意A到a∈B1∪A，由 B1，B2，f1的定義與 A 的性質(zhì)，x，y∈B1∪A，當(dāng) xy≠0 時有

3 全序“ ”與B2的改進(jìn)

4 計算Paley圖團(tuán)數(shù)的一個新方法

我們運用一般的計算機完成上述兩例的計算，耗時不到1s.

5 主要結(jié)果

在CPU為Intel·i3/2100的計算機上，我們完成上述運算大約耗時70h。

[1]Ramsey F P.On a problem of formal logic[N].Proceedings of the London Mathem aticalSociety,1930,30:264～286.

[2]R.L.Graham,B.L.Rothschild,J.H.Spencer.Ram sey theory[M].JohnWiley&Sons,1990.

[3]李喬.拉姆塞數(shù)理論[M].長沙:湖南教育出版社.1991.

[4]李喬.組合數(shù)學(xué)基礎(chǔ)[M].北京:高等教育出版社,1993.

[5]P.Erd·s.Some remarks on the theory of graphs[J].Bulletin of the American Mathematical Society,1947,53:292～294.

[6]R.E.Greenwood and A.M.Gleason,Combinatorial relations and chromatic grap hs[J].Canadian JournalofMathematics,1955(7):1～7.

[7]S.P.Radziszowski.Small Ramsey Numbers[J].The Electronic Journalof Combinatorics,View the Journal,Dynam ic Surveys,2011,August22 ElJC revision#13,2011,DS1.13:1～84

[8]Luo Haipeng,SuWenlong,Li Zhengchong.The properties of self-complementary graphsand new lower bounds for diagonal Ramsey numbers[J].Australasian Journal of Combinatorics,2002(25):103～116.

[9]SuWenlong,Luo Haipeng,LiQiao,Lowerbounds formulticolor Classical Ramsey Numbers[J].Science in China(seriesA),1999,42(10):1019～1024.

New Lower Bounds for Diagonal Ram sey Numbers R（22，23）

Xu Chengzhang1,Liang W enzhong2
(1.2.W uzhou University,W uzhou 543002,China)

The paper studies the lower bounds for Ramsey numbers.In light of a new discovery automorphism of Paley Graphs,a new method of computing clique numbers of Paley graphs is proposed,which sheds new light on solving the problem raised by Radziszowski.Staged results are obtained:the clique number of Paley graphs with order 14813 is computed and a new lower bound for diagonal Ramsey numbers R（23，23）≥29629 is obtained.

Ramsey number;lower bound;Paley graph;clique number;automorphism

O157

A

1673-8535（2012）02-0075-06

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

梁文忠（1963－），男，廣西賀州人，梧州學(xué)院副教授，研究方向：組合數(shù)學(xué)的研究。

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

2012-01-12

國家自然科學(xué)基金資助項目（60563008）；廣西自然科學(xué)基金項目（0991278）；廣西教育廳科研項目(200911LX433)；梧州學(xué)院科研項目(2009B013，2009B011)資助