涂巧霞,王 艷

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

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

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

1 相關(guān)定理

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

定理1若B2=K2+2K1,Kn是具有n個(gè)頂點(diǎn)的完全圖,則對(duì)足夠大的n,一定有

(1)

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

推論1若B2=K2+2K1,Kn是具有n個(gè)頂點(diǎn)的完全圖,則對(duì)足夠大的n,一定有

(2)

2 相關(guān)引理

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

(3)

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

α(G)≥Nfa+1(d)

(4)

(5)

3 主要證明

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

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

(6)

(7)

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

(8)

于是

E[YT]=Pr[BT]=p6

(9)

進(jìn)一步,令

(10)

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

(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)

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

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

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