許成章，梁文忠

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

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

許成章1，梁文忠2

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

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

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

1 引言

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

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

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

1947年匈牙利數(shù)學(xué)家Erdǒs[5]首創(chuàng)概率方法得到對(duì)角Ramsey數(shù)下界的漸近估計(jì).1955年美國(guó)數(shù)學(xué)家Greenwood和Gleason[6]首創(chuàng)構(gòu)造性方法，得到歷史上第一批Ramsey數(shù)的準(zhǔn)確值，其中兩個(gè)對(duì)角Ramsey數(shù)是這樣得到的：首先利用Paley圖計(jì)算出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型素?cái)?shù)的二次剩余構(gòu)造的循環(huán)圖。美國(guó)學(xué)者Radziszowski的動(dòng)態(tài)綜述論文[7]記錄了幾十年來(lái)學(xué)術(shù)界計(jì)算Paley圖的團(tuán)數(shù)和研究對(duì)角Ramsey數(shù)的非常緩慢的進(jìn)程：直到2002年，羅海鵬、蘇文龍等學(xué)者方才計(jì)算出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)新，推動(dòng)Ramsey數(shù)的研究進(jìn)展，在http://www.cs.rit.edu/～spr/topics.html中提出如下問(wèn)題：

“計(jì)算20000階以?xún)?nèi)的Paley圖的團(tuán)數(shù)”。

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

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

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

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

引理 A[9]設(shè) B= ｛x｜x∈A，x-1∈A｝，Gp在 B上的導(dǎo)出子圖記為Gp[B]，則Gp[B]有如下六個(gè)自同構(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)確定的等價(jià)關(guān)系“～”把B分拆成如下若干個(gè)等價(jià)類(lèi)。其中代表元是α的等價(jià)類(lèi)記為〈a〉各等價(jià)類(lèi)代表元形成的集記為N 。

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

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

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

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

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

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

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

我們運(yùn)用一般的計(jì)算機(jī)完成上述兩例的計(jì)算，耗時(shí)不到1s.

5 主要結(jié)果

在CPU為Intel·i3/2100的計(jì)算機(jī)上，我們完成上述運(yùn)算大約耗時(shí)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].長(zhǎng)沙:湖南教育出版社.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é)任編輯：高 堅(jiān)）

2012-01-12

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