用圖的分割原理計(jì)算一些Ramsey數(shù)

裴超平

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

?

用圖的分割原理計(jì)算一些Ramsey數(shù)

裴超平

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

摘要：Ramsey數(shù)R(G,H)為最小的正整數(shù)N，使得對完全圖KN的邊集的任意紅藍(lán)二著色，都存在紅色的子圖G或者藍(lán)色的子圖H.結(jié)合Burr的一個(gè)定理和圖的分割原理，證明當(dāng)n≥|G|2+2χ(G)α(G)時(shí)，R(Pn,G)=(χ(G)-1)(n-1)+σ(G).

關(guān)鍵詞：Ramsey數(shù)； Ramsey 完備性； 路徑

1研究內(nèi)容

本文所討論的圖都是簡單圖.對于給定的圖G和H，Ramsey數(shù)R(G,H)為最小的正整數(shù)N，使得對完全圖KN的邊集的任意紅藍(lán)二著色，都存在紅色的子圖G或者藍(lán)色的子圖H.設(shè)Δ(G)為圖G的最大度，χ(G)為圖G色數(shù)，α(G)為G的最大獨(dú)立集所含頂點(diǎn)數(shù)，σ(G)為G的著色剩余，即對G的頂點(diǎn)集的任意χ(G)-真著色中最小的顏色集所包含的頂點(diǎn)數(shù).Burr[1]得到如下的下界.

引理1給定圖G和連通圖H，|H|≥σ(G)，則:

稱H是G-good，如果引理1中的等式成立.Burr[1]證明了如果連通圖H含有一條充分長的懸掛路徑且|H|≥σ(G)，則H是G-good的.由此引出一個(gè)問題：對于給定的圖G，H中的懸掛路徑有多長就能保證H是G-good ? 這個(gè)問題的難度非常高，因?yàn)镽amsey 數(shù)的求解一直是數(shù)學(xué)上具有挑戰(zhàn)的問題之一.因此研究一個(gè)更具體的問題：路徑Pn有多長，能保證Pn是G-good？Allen等[2]猜想只要n≥χ(G)|G|就可以.

圖的分割原理是近年來圖論新興起的課題之一，它研究的是對完全圖的邊集進(jìn)行二著色后，其頂點(diǎn)集可以被多少條不相交的路徑或者圈覆蓋.Pokrovskiy[3-4]證明了如下定理：

定理1對于任意的正整數(shù)k，以及n≥k，假設(shè)Kn的邊集被紅藍(lán)兩種顏色著色.則Kn的頂點(diǎn)集可以被k條不相交的紅色路徑和一個(gè)不相交的每個(gè)部集都相等的藍(lán)色完全(k+1)-部圖覆蓋.這里的路徑和完全多部圖可以是空集.

用定理1可以求解出關(guān)于路徑的Ramsey數(shù)R(Pn,G).

定理2對于給定的圖G，當(dāng)n≥|G|2+2χ(G)·α(G)時(shí)，R(Pn,G)=(χ(G)-1)(n-1)+σ(G).

2定理證明

為了證明定理2，回顧一下Burr的定理.

定理3[1]設(shè)G是一個(gè)具有p個(gè)頂點(diǎn)的圖.令H為含n個(gè)頂點(diǎn)的連通圖，并且含一條長度為m的懸掛路徑.設(shè)G1是G中刪除含u個(gè)頂點(diǎn)的獨(dú)立集所得到的圖，H1是H的懸掛路徑縮減1后的得到的圖.如果m≥(p-2)(p-u)+u+1，則:

考慮H=Pn，即n≥|G|2時(shí)，有R(Pn,G)≤max(R(Pn-1,G),R(Pn,G1)+n-1).

設(shè)k=χ(G).由于k=1的情況是平凡的，假設(shè)k≥2.

設(shè)n0=|G|2+2(k-1)α(G).歸納假設(shè)當(dāng)n≥n0時(shí)，R(Pn,G1)=(k-2)(n-1)+σ(G).證明當(dāng)n≥|G|2+2kα(G)時(shí)，R(Pn,G)=(k-1)(n-1)+σ(G).由定理3得：

重復(fù)應(yīng)用定理3，可以得R(Pn-1,G)≤max(R(Pn-2,G),(k-1)(n-1)+σ(G)).于是，

R(Pn,G)≤max(R(Pn-2,G),(k-1)(n-1)+σ(G))≤…≤max(R(Pn0,G),(k-1)(n-1)+σ(G))

設(shè)h=(χ(G)-1)(n0-1)+kα(G).由定理1，對完全圖Kh的任意紅藍(lán)二著色，其頂點(diǎn)集可以被k-1條不相交的紅色路徑和1個(gè)不相交的藍(lán)色等部集的完全k部圖覆蓋.如果這k-1條路徑中不存在紅色Pn0，則顯然會(huì)存在藍(lán)色的Kk(α(G))，從而含有一個(gè)藍(lán)色的圖G.所以，得到R(Pn0,G)≤(k-1)(n0-1)+kα(G).

由條件n≥|G|2+2kα(G)=n0+2α(G)以及k≥2，可得:

(k-1)(n-1)+σ(G)≥(k-1)(n0-1)+(2k-2)·α(G)≥(k-1)(n0-1)+kα(G)；

所以

R(Pn,G)≤max(R(Pn0,G),(k-1)(n-1)+

σ(G))≤(k-1)(n-1)+σ(G)，

得證.

3展望

相信，如果能夠縮小定理3中關(guān)于懸掛路徑的條件，就能夠求出使得Pn是G-good的更嚴(yán)格的條件.而如果能給出R(Cn0,G)的約束條件的話，可以將這個(gè)結(jié)論推廣到圈上.

參考文獻(xiàn):

[1]Burr S A. Ramsey numbers involving graphs with long suspended paths [J]. Journal of the London Mathematical Society, 1981, 24(2): 405.

[2]Allen P, Brightwell G, Skokan J. Ramsey-goodness and otherwise [J].Combinatorica, 2013, 33(2): 125.

[3]Pokrovskiy A. Partitioning edge-colored complete graphs into monochromatic cycles and paths [J]. Journal of Combinatorical Theory Series B, 2014, 106: 70.

[4]Pokrovskiy A. Partitioning edge-coloured complete graphs into monochromatic cycles[J]. Electronic Notes in Discrete Mathematics,2013,43:311.

Using Partitioning Graphs to Calculate Some Ramsey Numbers

PEI Chaoping

(Department of Mathematics, Tongji University, Shanghai 200092， China)

Abstract：Ramsey number is the smallest integer N such that for any red-blue edge-coloring of KN, there is a red subgraph G or a blue subgraph H. In this paper, we use a theorem of Burr and the method of partitioning graphs to prove that if n≥|G|2+2χ(G)α(G), then R(Pn,G)=(χ(G)-1)(n-1)+σ(G).

Key words：Ramsey numbers； Ramsey goodness； path

文獻(xiàn)標(biāo)志碼：A

中圖分類號(hào)：O157.5

收稿日期：2015-04-23

第一作者： 裴超平(1989—)，男，博士生，主要研究方向?yàn)榻M合數(shù)學(xué)和圖論，E-mail:peichaoping@msn.cn