一類廣義Ramsey數(shù)R(B2,Kn)界的研究

涂巧霞,王 艷

(黃岡師范學院 數(shù)學與統(tǒng)計學院,湖北 黃岡 438000)

Ramsey理論是組合數(shù)學的一個重要分支,它廣泛應用于計算機科學、信息論以及決策學等領域.在Ramsey理論研究中,關于求解Ramsey數(shù),在邏輯分析、并行計算和計算幾何等計算機科學領域起著至關重要的作用,同時,許多實際問題的求解,如貯藏問題等等,也往往導致求一個相關圖的Ramsey數(shù).

一般地,確定Ramsey數(shù)是一個非常困難，且尚未完全解決的問題.可以通過構造一些特殊的極值圖,從而得到它的下界或上界.如,C5不含K3,同時有C5的補圖也是C5,于是對于完全圖K5的這樣一種紅藍著色,將子圖C5染成紅色,余下邊同樣構成一個C5,染成藍色,此種著色既不含紅K3,也不含藍K3,所以有R(3,3)>5;在C8中增加四條對角線形成一個獨立數(shù)為3的無三角形圖,在完全圖K8中,將上述加了四條對角線的C8這樣的子圖染成紅色,余下邊染成藍色,于是這種染色既不含紅色三角形,也不含藍色K4,故有R(3,4)>8.

1 相關定理

利用概率方法作有關Ramsey數(shù)和一些特殊圖的Ramsey數(shù)的研究[2-7].本質上概率方法是一種粗糙的計數(shù)論證方法,但一方面可以用來斷定具有某種特性的圖的存在性,另一方面,一定程度上給出了Ramsey數(shù)的一些非線性的界.應用概率方法,可以得出一類廣義Ramsey數(shù)的非線性界.

定理1若B2=K2+2K1,Kn是具有n個頂點的完全圖,則對足夠大的n,一定有

(1)

由于B2是完全圖K4的子圖,因此,定理1的界同樣也適用于Ramsey數(shù)R(4,n).

推論1若B2=K2+2K1,Kn是具有n個頂點的完全圖,則對足夠大的n,一定有

(2)

2 相關引理

引理1設N=N(n),n=o(N)(n→∞),那么任意ε>0,若n足夠大,則有

(3)

引理2令G為階為N的圖,平均次數(shù)為d,若G中任意頂點v的鄰域N(v)生成子圖G[N(v)]的最大次不超過a,那么

α(G)≥Nfa+1(d)

(4)

(5)

3 主要證明

本文主要對定理1中出現(xiàn)的式(1)利用概率方法給出證明.

定理1的證明:令B2=K2+2K1,易看出B2=K4-e,Kn是具有n個頂點的完全圖,文中主要利用概率方法尋找一類特殊R(B2,Kn)數(shù)的上下界，首先考慮下界,考慮在概率空間G(N,p)中的隨機圖.S是階為n的點集,構造指示函數(shù)如下：

(6)

(7)

類似構造函數(shù)YT如下:

(8)

于是

E[YT]=Pr[BT]=p6

(9)

進一步,令

(10)

據(jù)數(shù)學期望的線性性質,有

(11)

(12)

尋找合適的N使得|G*|盡可能大，可以考慮取

(13)

則有

(14)

據(jù)引理1,又有

(15)

(16)

(17)

為了證明廣義Ramsey數(shù)R(B2,Kn)的上界,任取階為N=R(B2,Kn)-1的圖G,且圖G不含B2,并有α(G)

(18)

所以

(19)

經典Ramsey數(shù)R(k,l)的確定,已知R(1,n)=1和R(2,n)=n, 并且有R(k,l)=R(l,k),故只須考慮k和l均大于2的情形，表1給出已確定的經典Ramsey數(shù).

表1 已確定的經典Ramsey數(shù)R(k,l)

其它尚未給出精確值的經典Ramsey數(shù)R(4,n)目前已有相關界的討論,大多數(shù)界均為組合數(shù)形式或者遞推式,均為構造特殊圖的方法得出.推論1給出的Ramsey數(shù)R(4,n)界的確定一定程度上給出了經典Ramsey數(shù)R(4,n)精確值的取值范圍.