用自同構循環圖計算Ｒａｍｓｅｙ數Ｒ（３，ｑ）的下界

(1.梧州學院， 廣西 梧州 543002; 2.華南師范大學， 廣州 510631; 3.廣西科學院， 南寧 530003)



摘 要：

確定經典Ramsey數的下界是組合數學中非常困難的問題，因而人們常用各種方法計算它的界。發現一種新的方法， 即自同構循環圖的方法，計算得到三個經典Ramsey數的新下界：R(3，30)≥188，R(3，33)≥217，R(3，34)≥225。

 關鍵詞：Ramsey數； 下界； 自同構循環圖

 中圖分類號：O1575 文獻標志碼： A

文章編號：10013695(2008)12358102



Lower bounds for R(3，q) based on automorphism cyclic graphs

SU Wenlong1， WU Kang2， LUO Haipeng3， XU Xiaodong3



(1.Wuzhou University， Wuzhou Guangxi 543002， China;

2.South China Normal University， Guangzhou 510631， China; 3.Guangxi Academy of Sciences， Nanning 530003， China)



Abstract:

It is a very difficult problem to give lower bounds for classical Ramsey numbers in combinatorics，so people use many different methods to compute their bounds. This paper gave a new method based on automorphism cyclic graphs，and got new lower bounds for three Ramsey numbers: R(3，30)≥188，R(3，33)≥217，R(3，34)≥225.

 Key words：Ramsey number; lower bound; automorphism cyclic graph



0 引言

確定Ramsey數是組合數學中非常困難的問題^[1]。1955年，R.E.Greenwood等人^[2]在確定歷史上第一批Ramsey數準確值時， 曾用循環圖得到R(3，3)≥6、R(3，4)≥9、R(3，5)≥14、R(4，4)≥18 等下界。后世的學者沿用這種方法得到一些新的成果，動態綜述文獻[3]及時記錄了這些成果并附有大量參考文獻。

計算圖的團數是用循環圖研究經典Ramsey數下界的最主要的困難。近年來，在文獻[4~8]中用素數階循環圖研究經典Ramsey數的下界，能夠充分運用有限域的性質提高運算效率。例如在文獻[4]中指出，利用自補圖的同構性質可提高計算團數的運算效率，從而得到R(17，17)≥8 917，R(18，18)≥11 005和R(19，19)≥17 885等新下界；在文獻[5~8]中利用有限域的三次剩余或高次剩余構造循環圖，得到R(3，31)≥198，R(4，12)≥128，R(6，16)≥434，R(6，17)≥548，以及R(3，3，12)≥182，R(3，3，13)≥212等新下界。 這些下界被文獻[3]等多種文獻所引用，是迄今已知的最好結論。然而，把素數階循環圖的方法推廣到一般階循環圖并非易事，因為后者以整數環Zn為背景，再也不能像前者那樣利用有限域Zp的特殊性質。注意到自同構是推導素數階循環圖的許多性質的重要工具，本文運用這個工具研究一般階循環圖，發現了一種新的方法，即自同構循環圖的參數集也具有類似于素數階循環圖的某些性質，也能提高計算圖的團數運算效率。 

1 自同構循環圖的若干性質

給定整數n≥8，令m＝[n/2]。對于整數s＜t，記[s，t]＝{s，s+1，…，t}。令

Zn＝ [-m，m]，當n是奇數[1-m，m]，當n是偶數

以下除非特別說明，所有模n整數的運算結果都理解為模n后屬于Zn，并用通常的等號“＝”表示“模n相等”。

定義1對于集合S＝[1，m]的一個2部分拆S＝S1∪S2，記Ai＝{x||x|∈Si }，設n階完全圖Kn的頂點集V＝Zn，邊集E是Zn的所有2元子集的集且有分拆E＝E1∪E2。其中：

Ei＝{{x，y}|{x，y}∈E且x-y∈Ai }; i＝1，2。

把Ei中的邊叫做Ai色的，記Kn中Ai色邊導出的子圖為Gn(Ai)，其團數記為[Gn(Ai)]。這里i＝1，2。于是本文按照參數集合A1或A2(即S1或S2)把Kn的邊2染色，得到n階循環圖Gn(Ai)，稱Gn(Ai)是由參數集Si生成的。

根據Ramsey定理^[1]，顯然有 R([Gn(A1)]+1，[Gn(A2)]+ 1)≥n+1。

引理1設k∈Zn且(k，n)＝1，則Zn到自身的變換f : x| →kx是Gn(Ai)的同構變換。

一般地，變換f把參數集Si變換成S*i，Gn(Ai)變換成另一個循環圖Gn(A*i)。這里S*i＝{|kx||x∈Si}，A*i＝{kx|x∈Ai }。特別地，當Gn(A*i)＝Gn(Ai)時有如下定義。

定義2對于參數集Si，如果存在k∈Zn且(k，n)＝1，使kAi＝Ai，那么就把Zn到自身的變換f : x| →kx稱為Gn(Ai)的自同構變換；Gn(Ai)稱為自同構循環圖；Si稱為自同構參數集；k稱為Gn(Ai)的特別元，也稱為Si的特別元，或者稱為n的特別元。

顯然，k=1與-1可視為一般階循環圖Gn(Ai)的特別元，稱這樣的特別元是平凡的。如果自同構循環圖Gn(Ai)僅有平凡的特別元，就說它是平凡的。

約定以下說到的自同構循環圖都是非平凡的。如果存在整數k∈[2，m] 且(k，n)＝1與最小整數s≥2使|ks|＝1成立，就稱k為n的s階特別元。由定義2即得引理2。

引理2Gn(Ai)是自同構循環圖的充要條件是：存在s≥2階特別元k，使參數集Si滿足a∈Ai ka∈Ai(即a∈Si|ka|∈Si)。

定義3在Gn(Ai)中，如果存在自同構變換f使f(a)＝b，就稱a與b等價。與a等價的元做成一個等價類，記為〈a〉，稱a為〈a〉的代表元。

按等價關系可以把Ai分拆成若干個等價類。由引理2得a∈Aika∈Aik2a∈Ai…，因此f : x| →±kjx(0≤j≤s-1)是Gn(Ai)的自同構，由定義3即得引理3。

引理3設k是自同構循環圖Gn(Ai)的s階特別元，則有等價類〈a〉＝{a，-a，ka，-ka，…，ks-1a，-ks-1a }，它的階數|〈a〉|是2s的正因數。

注意到Gn(Ai)是頂點可遷的，易知Gn(Ai)的團數等于Gn(Ai)中含頂點0的團的最大階，因此只須考察含頂點0的團。 根據定義1可知這樣的團的其他非零頂點是Ai的元，故有引理4。 

引理4記圖Gn(Ai)中頂點集為Ai的導出子圖為Gn[Ai]，其團數為[Ai]，則有[Gn(Ai)]＝[Ai]+1。

于是求Gb(Ai)的團數就轉換為求Gb[Ai]的團數。為了求得[Ai]，引進Ai的一個全序。

定義4設x∈Si，記di(x)＝|{y∈Ai : x-y∈Ai}|。在Ai上的序規定如下:

a)Ai中的子集〈a〉＝{a，-a，ka，-ka，…，ks-1a，-ks-1a }對于序構成區間，并且a-a ka-ka…ks-1a-ks-1a。

b)對于Ai中分屬不同子集的元x∈〈a〉＝{a，-a，ka，-ka，…，ks-1a，-ks-1a}和y∈〈b〉＝{b，-b，kb，-kb，…，ks-1b，-ks-1b }，規定xy當且僅當di(a)＜di(b)，或者當di(a)＝di(b)時a＜b。

必須指出兩點注意：（a）在Ai的子集{a，-a，ka，-ka，…，ks-1a，-ks-1a }中至少有一個元屬于Si;（b）對于任意a，y∈Ai，由引理2可知a-y∈Ai±kj(a-y)∈Ai。其中0≤j≤s-1。由此易知di(a)＝di(-a) 與 di(a)＝di(kja)，即得di(a)＝di(-a)＝di(ka)＝di(-ka)＝…＝di(ks-1a)＝di(-ks-1a)。

由這兩點注意可知序是明確定義的，并且(Ai，)是全序集。xy稱為x前于y。

引理5記全序集(Ai，)中所有等價類的代表元的集合為M。如果對于任意x∈M ，恒有di(x)＝0，那么[Ai]＝1。

證明否則，設對于任意x∈M，恒有di(x)＝0，且有[Ai]≥2，則[Gn(Ai)]≥3，在圖Gn(Ai)中有3階團{0，x，y}。其中x，y∈Ai且x-y∈Ai。有如下情形：

如果x或y∈M，就有di(x)≥1或di(y)≥1，與已知條件矛盾。 

如果-x與-y∈M，則由引理1知{0，-x，-y}也是圖Gn(Ai)的3階團，就有di(-x)≥1，與已知條件矛盾。證畢。

定義5全序集(Ai，)上的長為t(t≥1) 的鏈x0x1…xt稱為起點為x0的長為t的Ai色的鏈，如果對于0≤h＜j≤t有xh-xj∈Ai。起點是x0的鏈的最大長記為li(x0)。如果起點是x0的長為t≥1的鏈不存在，就令li(x0)＝0。

引理6[Ai]＝1+max{li(a) : a∈M}。

證明設[Ai]＝1，即對于任意a∈M與y∈Ai，恒有y-aAi，據定義5有li(a)＝0。此時就有max{li(a) : a∈M}＝0，引理6成立。以下考察[Ai]≥2的情形。

設t＝max{li(a) : a∈M}≥1，則在Gn[Ai]中存在長為t的Ai色的鏈x0x1…xt，據定義5可知這條鏈的t+1個元構成Gn[Ai] 的一個團，即得[Ai]≥1+t＝1+max{li(a) : a∈Si}。以下再證1+max{li(a) : a∈M}≥[Ai]。

設[Ai]＝1+t≥2，則在Gn[Ai]中存在若干個t+1階團。據定義5可知，這些t+1階團在(Ai，)上構成長為t的鏈，再在(Ai，)上所有長為t的鏈中取起點按來說最前面的一條，記為x0x1…xt。筆者斷言一定有x0∈M。

假若不然，即x0所在的等價類中有另一個元為代表元，不妨設kx0∈M。作Zn到自身的變換f : x| →kx，由引理1知這是Gn(Si)的同構變換，從而也是Gn[Ai] 的同構變換，它把Gn[Ai] 中t+1個頂點的團{x0，x1，…，xt}變成另一個團{kx0，kx1，…，kxt }。據定義5可知，這t+1個元kx0，kx1，…，kxt在(Ai，)上構成長為t的鏈。由定義4所規定的全序集(Ai，)的排序方式可知這條鏈可表示為kx0kx1…kxt，其起點kx0x0。因此原來給定的鏈x0x1…xt不是“起點按來說最前”的一條，矛盾。

于是斷言x0∈M為真。故有1+max{li(a) : a∈M}≥1+t＝[Ai]。引理6得證。

例1：給定n＝35與3階特別元k＝11，設S1＝{1，7，11，16}，根據引理2知Gn(Ai)是自同構循環圖。容易證明Gn(A1)的團數[Gn(A1)]＝2。

為了計算Gn(A2)的團數，據引理3把A2分拆成下述五個等價類:

〈2〉＝{2，-2，-13，13，-3，3}

〈14〉＝{14，-14}

〈4〉＝{4，-4，9，-9，-6，6}

〈5〉＝{5，-5，-15，15，10，-10}

〈8〉＝{8，-8，-17，17，-12，12} 

按定義5做全序集(A2，)， 得到所有等價類的代表元的集合為M＝{2，14，4，5，8}。計算以a∈M為起點的A2色的鏈，得到第一條長為6的A2色鏈2-24-4-668。 

此后沒有更長的A2色鏈，根據引理6有[A2]＝1+max{l2(a) : a∈M}＝7和[Gn(A2)]＝[A2]+1＝8。由Ramsey定理即得R(3，9)≥36。

已知R(3，9)＝36，因此例1得到的結論是R(3，9) 的下確界。

通過這個簡單的例子指出，本文的理論和方法是非常有效的。一般地，對于較大的整數n及較大的團數[A2]，用回溯法計算以xj∈S2為起點的A2色鏈的運算量非常巨大。注意到，引理6表明，為了計算Gn[Ai]的團數，只須尋求以a∈M為起點的最長的鏈即可。注意到大多數等價類都是2s元子集，根據引理6，不必計算非代表元為起點的鏈，所需要的工作量即可減少為原來的1/2s。

 此外，根據據定義4的(Ai，)的排序方式是“按頂點的度數小者優先”的原則，這樣又能夠把運算效率提高若干倍。綜合起來，就能夠使計算團數的運算效率提高數十倍。

2 結束語

定理1R(3，30)≥188，R(3，33)≥217，R(3，34)≥225。

證明為了節省篇幅，除了在a）中給出了自同構循環圖Gn(A2)中第一條長為[A2]-1的A2色鏈之外，本文只寫出給定的n、k、S1，以及計算得到的R(3，q)的新下界。

a)給定n＝187與2階特別元k＝67，令S1＝{1，3，8，14，25，34，40，46，52，62，67，69，88，90}。據引理2知Gn(Ai)是自同構循環圖。容易證明[Gn(A1)]＝2。計算以a∈M為起點的A2色的鏈，得到第一條長為27的A2色鏈：

2010-10-81-6464205827-27-4376-76-55-92-17-223238-38 85-85-53 5348-48-6674。

此后沒有更長的A2色鏈，據引理6有[A2]＝1+max{l2(a) : a∈M}＝28。據引理4有[Gn(A2)]＝[A2]+1＝29。根據Ramsey定理有R(3，30)≥188。

b)給定n＝216與3階特別元k＝71，令S1＝{1，3，16，21，30，45，54，56，63，71，73，78，88，96，102}，據引理2知Gn(Ai)是自同構循環圖。計算得R(3，33)≥217。

c)給定n＝224與2階特別元k＝111，令S1＝{1，3，18，23，28，30，34，40，44，50，82，89，96，104，109，111}，根據引理2知Gn(Ai)是自同構循環圖。計算得R(3，34)≥225。

筆者在CPU為AMD3600+的計算機上完成上述運算的時間約為6 h。

參考文獻：

[1]BONDY J A， MURTY U S R. Graph theory with applications[M]. [S.l.]:The Macmillan Press Ltd， 1976.

[2] GREENWOOD R E， GLEASON A M. Combinatorial relations and chromatic graphs[J].Canadian Journal of Mathematics， 1955， 7 (1):17.

[3] RADZISZOWSKI S P. Small Ramsey numbers[J].The Electronic Journal of Combinatorics，2006， 11 :160.

[4] LUO Haipeng， SU Wenlong， LI Zhenchong. The properties of selfcomplementary graphs and new lower bounds for diagonal Ramsey numbers[J].Australasian Journal of Combinatorics，2002(25):103116.

[5] SU Wenlong， LUO Haipeng， ZHANG Zhengyou， et al. New lower bounds of fifteen classical Ramsey numbers[J].Australasian Journal of Combinatorics， 1999(19):9199.

[6] 蘇文龍，羅海鵬，李喬.經典Ramsey數R(4，12)，R(5，11)和R(5，12)的新下界[J].科學通報，1997， 42 (22):2460.

[7] SU Wenlong， LI Qiao， LUO Haipeng， et al. Lower bounds of Ramsey numbers based on cubic residues[J].Discrete Mathematics，2002， 250 (1):197209.

[8] LUO Haipeng， SU Wenlong， SHEN Yunqiu. New lower bounds for two multicolor classical Ramsey numbers[J].Radovi Matematicki， 2004， 13 :1521.