林晶12

(1. 福建工程學院 數(shù)理學院， 福建 福州 350118；2. 福州大學 離散數(shù)學研究中心， 福建 福州 350116)

給定一個圖G，令f(G)表示G的二部子圖包含的最大邊數(shù)。給定一個正整數(shù)m，令f(m)表示所有具有m條邊的圖G的f(G)的最小值。經(jīng)典的最大割問題旨在尋找f(m)的值，該問題有非常廣泛的應(yīng)用價值，被應(yīng)用于復(fù)雜網(wǎng)絡(luò)社團結(jié)構(gòu)分析、大規(guī)模集成電路設(shè)計(VLSI)，同時也在統(tǒng)計物理學中用來研究處理自旋玻璃(Spin glass)狀態(tài)的重要模型之一。

猜想0.1[7]. 對于任意給定的圖H，存在常數(shù)ε(H)>0，使得f(m,H)≥m/2+Ω(m3/4+ε)。

提高猜想0.1中下界的誤差項非常困難，即使相對簡單的圖H。到目前為止，引起國內(nèi)外學者最廣泛研究的情況是H=K3。在諸多研究[8-10]之后，Alon[2]證明了對所有的m，f(m,K3)至少是m/2+Ω(m4/5)，且這個下界是緊的。Alon, Krivelevich和Sudakov[11]進一步延伸了該結(jié)論：令H由單個頂點連接某一棵非平凡樹的所有頂點構(gòu)成的圖，存在一個常數(shù)c=c(H)>0，使得對所有的m，均有f(m,H)至少是m/2+cm4/5，且這個界是緊的。最近，Zeng和 Hou對H是完全圖的情形[12]和H是奇圈的情形[13]分別給出了相應(yīng)的下界。

森林是不含圈的圖，想進一步研究當H是由單個頂點連接某個含圈圖的所有頂點構(gòu)成的圖時，f(m,H)的下界情況。在含圈圖中，最典型的就是圈或完全二部圖K2,s。因此，本文將考慮猜想0.1，當H是一個偶輪或者H是單個頂點連接任意多個不交的K2,s的所有頂點構(gòu)成的圖。無特別說明，本文中的圖均為有限無向簡單圖，所有的對數(shù)均以e為底。設(shè)G和H是兩個不交的圖，將G和H的不交記作G∪H。

1 單點連接的情形

延續(xù)文獻[2,7,11]中的討論，并附加一些新的思想，需要用到一些已知的結(jié)論。首先，介紹下述引理，它在證明中起到至關(guān)重要的作用，揭示了一個染色數(shù)“較小”的圖必包含一個“較大”的二部子圖。詳細證明可參考文獻[2,7,11,14]。

下面的3個引理，分別用不同的參數(shù)給出了圖G的f(G)的不同下界。

其次，介紹一個不含單邊最大度大等于2的二部圖的圖的邊數(shù)上界。

引理1.6[16]令H是一個二部圖且它的其中一部分頂點的最大度為Δ′≥2。若G是一個有n個頂點且不含H的圖，那么存在一個常數(shù)b=b(H)>0，使得e(G)≤bn1-1/Δ′。

最后，介紹一個引理，它闡述了對于具有相對大的最小度且每個頂點的鄰居導(dǎo)出子圖較稀疏的圖來說，必存在某個滿足指定條件的隨機導(dǎo)出子圖。

引理1.7[12]設(shè)G=(V,E)是一個有n個頂點、m條邊且最小度為mα的圖，其中α∈(0,1)是一個固定的實數(shù)。假設(shè)m充分大，且存在某個常數(shù)s>0,使得任意一個度為d的頂點v∈V,v的鄰居的導(dǎo)出子圖至多包含sd3/2條邊。那么，對每一個常數(shù)η∈(0,1)，都存在一個G的導(dǎo)出子圖G′=(V′,E′)，滿足以下性質(zhì)：

·V′中任意一個在G中度為d的頂點v，v的鄰居在G′中的導(dǎo)出子圖至多有2η2sd3/2條邊。

情況1 假設(shè)G中存在一個階為N的頂點集U，使得U的導(dǎo)出子圖G′=G[U]的最小度至少為q。顯然，e(G′)≥qN/2。定義

其中，θ=θ(t)∈(0,1)是一個系數(shù)，它的值將在后面證明中給出。首先證明存在U′?U使得G′有一個U′的導(dǎo)出子圖G″=G[U′]，G″至少包含qN/4條邊且G″是O(r)-可染的。為得到這個結(jié)論，從U中均勻地隨機選取2t個頂點，有放回地獨立重復(fù)取r次，于是得到r個隨機頂點集，記為X1,X2,…,Xr。假設(shè)Xi={x1(i),x2(i),…,x2t(i)}，1≤i≤r，令X={X1,X2,…,Xr}，則顯然有|X|≤r。構(gòu)造隨機頂點集U′，將U中任意一個頂點u放入U′，當且僅當存在某個Xi∈X,使得{ux1(i),ux2(i),…,ux2t(i)}?E(G′)。從而得到G′的一個導(dǎo)出子圖G″=G[U′]。

由于e(G′)≥qN/2且期望具有線性可加性，結(jié)合上式，得到

即G′中存在子圖G″至少包含qN/4條邊。

綜上，找到一個隨機頂點集X，|X|≤r，由X對應(yīng)了一個子圖G″?G至少包含qN/4條邊且是O(r)-可染的。下面，證明f(G)的下界。若N≥m(2t+1)/(3t+1),那么由引理1.3，

上式結(jié)合引理1.4以及q的定義，得到

其中，δ=δ(G′)是視需要而取定的常數(shù)。上述不等式結(jié)合引理1.4，可以得到

由定理1.1，可推出下述結(jié)論：

2 偶輪的情形

定理2.1令k≥2是一個正整數(shù)，W2k表示由單個頂點連接圈C2k的所有頂點構(gòu)成的輪圖。那么存在一個常數(shù)c(k)>0，使得對所有的m，均有

定理2.1的證明方法與上一節(jié)定理1.1的證明方法類似。介紹一個不含特定偶圈的圖的邊數(shù)上界。

引理2.2[17]假設(shè)k≥2是一個整數(shù)，假設(shè)G是一個有n個頂點且不含長度為2k的圈的圖，那么G中至多有100kn1+1/k條邊。

定理2.1的證明 假設(shè)k≥2是一個給定的實數(shù)，假設(shè)G=(V,E)是一個有n個頂點、m條邊且不含W2k的圖。因為C4=K2,2，所以由推論1.2可知，k=2時結(jié)論成立。因此下面假設(shè)k>2。定義q=m2k/(3k+2)，類似定理1.1的證明，根據(jù)G是否存在稠密子圖，分兩種情況進行討論。

從U中均勻地隨機取k個頂點，有放回地獨立重復(fù)取r次，于是得到r個隨機頂點集，記為X1,X2,…,Xr。記Xi={x1(i),x2(i),…,xk(i)}，X={X1,X2,…,Xr}。構(gòu)造頂點集U′如下：將U中任意一個頂點u放入U′中，當且僅當存在某個Xi∈X,使得{ux1(i),ux2(i),…,uxk(i)}?E(G′)。令G″=G[U′]。那么對U中的一個固定頂點u，事件不存在一個Xi∈X使得{ux1(i),ux2(i),…,uxk(i)}?E(G′)的概率至多是

固定上述的集合X和U′，對任意Xi∈X，令Gi是Xi中所有頂點的公共鄰居在G′中導(dǎo)出的子圖。因為G中不含W2k，故每一個Gi中不含K1,k，從而Gi是2(k+1)-可染的，所以G″是2(k+1)r-可染的。

若N

假設(shè)N≥m(2k+2)/(3k+2)，由引理1.3，

3 結(jié)論

2)令H由單個頂點連接K2,s的所有頂點構(gòu)成的圖。那么存在一個常數(shù)c(s)>0，使得f(m,H)≥m/2+c(s)m3/4。

3)設(shè)k≥2是一個正整數(shù)，W2k表示由單個頂點連接圈C2k的所有頂點構(gòu)成的輪圖。那么存在一個常數(shù)c(k)>0，使得f(m,W2k)≥m/2+c(k)m(2k+2)/(3k+2)。