不含H子圖的圖上的最大割下界

林晶12

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

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

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

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

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

1 單點(diǎn)連接的情形

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

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

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

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

最后，介紹一個(gè)引理，它闡述了對(duì)于具有相對(duì)大的最小度且每個(gè)頂點(diǎn)的鄰居導(dǎo)出子圖較稀疏的圖來(lái)說(shuō)，必存在某個(gè)滿(mǎn)足指定條件的隨機(jī)導(dǎo)出子圖。

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

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

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

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

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

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

綜上，找到一個(gè)隨機(jī)頂點(diǎn)集X，|X|≤r，由X對(duì)應(yīng)了一個(gè)子圖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是一個(gè)正整數(shù)，W2k表示由單個(gè)頂點(diǎn)連接圈C2k的所有頂點(diǎn)構(gòu)成的輪圖。那么存在一個(gè)常數(shù)c(k)>0，使得對(duì)所有的m，均有

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

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

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

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

固定上述的集合X和U′，對(duì)任意Xi∈X，令Gi是Xi中所有頂點(diǎn)的公共鄰居在G′中導(dǎo)出的子圖。因?yàn)镚中不含W2k，故每一個(gè)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由單個(gè)頂點(diǎn)連接K2,s的所有頂點(diǎn)構(gòu)成的圖。那么存在一個(gè)常數(shù)c(s)>0，使得f(m,H)≥m/2+c(s)m3/4。

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