Ramsey數(shù)和無三角的Cayley圖

厲明波，李雨生

（同濟(jì)大學(xué) 數(shù)學(xué)系，上海200092）

設(shè)H是一個(gè)加法群，H＊＝H＼｛0｝.一個(gè)H的子集A被說成是關(guān)于逆元封閉的，是指若x∈A，則－x∈A.對一個(gè)H＊逆元封閉的子集A，可定義一個(gè)圖GH（A）如下：它的點(diǎn)集是H，而｛x，y｝是一條邊當(dāng)且僅當(dāng)｜x－y｜∈A.圖GH（A）被稱為由A導(dǎo)出的Cayley圖.

本文里，群H是Zn＝｛0，1，…，n｝，即模n的整數(shù)加群.對于Zn的一個(gè)逆元封閉子集A，簡記由A生成的Cayley圖GZn（A）為Gn（A）.因Zn中x的逆元是n－x，故｛x，y｝是Gn（A）的一條邊當(dāng)且僅當(dāng)｜x－y｜∈A.有兩個(gè)平凡的Gn（A），其一是空圖，對應(yīng)的生成集A＝?，其二是圈Cn，對應(yīng)的生成集A＝｛1，n－1｝.下面的性質(zhì)是熟知的，參見文獻(xiàn)[1].

引理1 設(shè)A?Z＊n為逆封閉子集，則Gn（A）是點(diǎn)傳遞的，且點(diǎn)i的鄰域是

A＋i＝ ｛a＋i：a∈A｝

特別地，Gn（A）是｜A｜－正則的；Zn的任何子集S是一個(gè)獨(dú)立集當(dāng)且僅當(dāng)對S中任何兩個(gè)相異的元x和y都有｜x－y｜?A.

設(shè)m和q為正整數(shù)，定義Ramsey數(shù)r（m，q）為最小的正整數(shù)n使得任何階為n，不含Km的圖都有q元獨(dú)立集.以α（G）記圖G的獨(dú)立集.當(dāng)Gn（A）不含三角形且α（Gn（A））≤q，則r（3，q＋1）≥n＋1.Ramsey理論的發(fā)展，參見文獻(xiàn)[2].

集合A?Zn被說成是無和的，是指（A＋A）∩A＝?就是說，方程x＋y＝z在A中無解，這里x，y，z不必兩兩互異.顯然，無和集不包含零元素.計(jì)算將依據(jù)下面的結(jié)果.

定理1 設(shè)A，A′都是Z＊n中的逆元封閉子集.則有

（1）若A′?A，則Gn（A′）是Gn（A）的一個(gè)子圖，此時(shí)α（Gn（A′））≥α（Gn（A））.

（2）Gn（A）不含三角形當(dāng)且僅當(dāng)A是無和集.

（3）若A是無和集，則α（Gn（A））≥｜A｜.

證明 設(shè)A′?A，若｛x，y｝是Gn（A′）的一條邊，則｜x－y｜∈A′故｜x－y｜∈A，從而｛x，y｝是Gn（A）的一條邊.即Gn（A′）是Gn（A）的一個(gè)子圖，（1）得證.

為證明（2），先假定A是無和集，要證明Gn（A）不含三角形.顯然，一個(gè)圖不含三角形當(dāng)且僅當(dāng)它的任何鄰域不含邊.由引理1可知，Gn（A）是點(diǎn)傳遞的，點(diǎn)0的鄰域就是A.故要證Gn（A）不含三角形，只要證明A中任何兩點(diǎn)不相連.當(dāng)A只含一點(diǎn)，這是平凡的.否則設(shè)A＝｛x，y，…｝，其中x≠y.若x和y相連，｜x－y｜∈A，故存在z∈A使得x－y＝z或y－x＝z，等價(jià)于x＝y(tǒng)＋z或y＝x＋z，與A為無和集的假設(shè)矛盾.

另一方面，假定Gn（A）不含三角形，則點(diǎn)0的鄰域A不含任何邊.證明A是無和的.若x＋y＝z在A中有解，則顯然x≠z，這是由于A是的子集.同理y≠z.

情況1x＝y(tǒng)≠z.此時(shí)，有2x＝z，得x＝z＋（n－x），其中n－x∈A（因A對逆元封閉）.此時(shí)互異的三個(gè)元素0，z，n－x組成一個(gè)三角形，矛盾.

情況2x，y，z互異.此時(shí)，有z－x＝y(tǒng)∈A，得｜z－x｜＝y(tǒng)∈A或｜z－x｜＝－y∈A，故｛x，z｝是一條邊，而互異的三個(gè)元素0，x，z組成一個(gè)三角形，矛盾.

為證（3），設(shè)A是無和集.由（2）已知，Gn（A）不含三角形，因此點(diǎn)0的鄰域A沒有邊，從而A是一個(gè)獨(dú)立集，故α（Gn（A））≥｜A｜.

設(shè)Φ是一個(gè)集合族.其中A0∈Φ說成是最大的，是指A0所含元素是Φ中最多的，它被說成是極大的，是指若A0不可能是Φ中任何集合的真子集.顯然最大集必然是極大集，但極大集不必是最大集.可得下述推論.

推論 設(shè)Φ是的所有逆元封閉的無和集所成的集合族，且A0∈Φ使得

α（Gn（A0））＝ min｛α（Gn（A））：A∈Φ｝

則A0是極大的；且Gn（A0）不含三角形.故r（3，q＋1）≥n＋1，其中q＝α（Gn（A0））.

定理1及其推論并沒有肯定有一個(gè)最大無和集A產(chǎn)生的Cayley圖Gn（A）有最小的獨(dú)立數(shù).例如，若n≥4是一個(gè)偶數(shù)，A＝｛1，3，…，n－1｝，則A是逆元封閉的且無和的，而Gn（A）＝Kn／2，n／2是一個(gè)平衡的完全二部圖，故α（Gn（A））＝n／2，其獨(dú)立數(shù)很大.然而，由定理1及其推論可知，對于固定的n，在尋求由最小獨(dú)立數(shù)的Gn（A）的過程中，只要考慮那些極大（不僅是最大）的逆元封閉的無和集即可，這將節(jié)約計(jì)算機(jī)運(yùn)算時(shí)間.

將計(jì)算一些較小階的不含三角形的Cayley圖的獨(dú)立數(shù)，在同樣階的此類圖中，選擇那些獨(dú)立數(shù)最小的圖，從而獲得新的Ramsey數(shù)r（3，q）的下界，這些結(jié)果被列于表1中.改進(jìn)了r（3，q）的下界，27≤q≤38.那些被改進(jìn)的下界分別在文獻(xiàn)[3－5]獲得.對于Ramsey數(shù)的這些結(jié)果，可以參考文獻(xiàn)[5].

表1 當(dāng)27≤q≤38時(shí)r（3，q）新下界Tab.1 New lower bounds for r（3，q）with 27≤q≤38

算法主要步驟如下：

第一步，給定正整數(shù)n，搜索極大的逆元封閉的無和集A?Z＊n，計(jì)算α（Gn（A））；發(fā)現(xiàn)A使得α（Gn（A））達(dá)到最小.

第二步，加大n，重復(fù)第一步.

本文使用約束傳播算法.由于約束的限定，大大提高了搜索的速度.其中的一個(gè)約束選取的元素是無和的，另外一個(gè)約束選取的元素的個(gè)數(shù)不能大于設(shè)定的最大值.

在確定一個(gè)生成集A之后，運(yùn)算時(shí)間的主要部分是計(jì)算α（Gn（A））.其中對于n＝258，用于發(fā)現(xiàn)最小α（Gn（A））和相應(yīng)的A，用時(shí)超過一周.本文用子圖同構(gòu)來計(jì)算最大獨(dú)立數(shù)，可以提高計(jì)算最大獨(dú)立數(shù)的速度，值得進(jìn)一步研究.

計(jì)算結(jié)果見表2.在相同獨(dú)立數(shù)的Cayley圖Gn（A）中，本文僅列舉了n最大時(shí)的計(jì)算數(shù)據(jù).在這些表中，第一行是Gn（A）的階數(shù)n，其為有相同的獨(dú)立數(shù)的最大n；第二行是相應(yīng)的生成集A，它是逆元封閉且無和的；第三行是獨(dú)立數(shù)α（Gn（A））.

表2 集合A 和α（Gn（A）），2≤α（Gn（A））≤37Tab.2 Sets A andα（Gn（A））with 2≤α（Gn（A））≤37

[1] Godsil C，Royle G.Agebraic graph theory[M].Berlin：Springer，2001.

[2] Graham R，Rothschild B，Spencer J.Ramsey theory[M].New York：John Wiley ＆Sons，1990.

[3] Wu K，Su W，Luo H，et al.New lower bound for seven classical Ramsey numbers R（3，q）[J].Appl Math Lett，2009，22：365.

[4] Wu K，Su W，Luo H，et al.A generalization of generalized Paley graphs and new lower bounds for R（3，q）[J／CD].Electron J Combin，2010.

[5] Chen H，Wu K，Xu X，et al.New lower bound for nine classical Ramsey numbers R（3，t）[J].Journal of Mathematics，2011，31：582.