概率方法在Ramsey數(shù)理論中的應(yīng)用

【摘 要】概率方法在組合數(shù)學(xué)中有很廣泛的應(yīng)用，其中，Ramsey數(shù)理論是其中最為經(jīng)典的例子。本文首先介紹三種組合數(shù)學(xué)中常用的概率方法，再分別利用這三種方法得出對稱型Ramsey數(shù)的三種不同下界估計(jì)。

【關(guān)鍵詞】概率方法；Ramsey數(shù)

1.三種基本概率方法

組合數(shù)學(xué)中常會遇到以下問題：在一個基本的對象空間（一般是有限的）中，具有特定性質(zhì)的對象是否存在。如果在該對象空間上建立一個古典概型，那么這個問題就轉(zhuǎn)化為：這個特定性質(zhì)所對應(yīng)的事件A發(fā)生的概率P是否為0；再利用概率論的方法驗(yàn)算概率P是否為零，這就解決問題了。這就是利用概率方法解決組合數(shù)學(xué)問題的一般思路。根據(jù)所運(yùn)用的概率技巧的不同，概率方法分為很多類，其中最為基本的有三種概率方法：直接型概率方法，期望型概率方法和局部化引理型概率方法。

1.1.直接型概率方法

顧名思義，直接型概率方法就是直接驗(yàn)算事件A的概率P是否為零的方法。其一般思路是：原問題等價于驗(yàn)算的對立事件B的概率是否小于1，再將B轉(zhuǎn)化為若干個事件的并，再分別計(jì)算每個事件的概率，利用概率的次可加性，估計(jì)B的概率的上界，驗(yàn)算其是否小于1即可。

1.2期望型概率方法

數(shù)學(xué)期望的線性性決定了其計(jì)算的便利，期望型概率方法正是基于數(shù)學(xué)期望的計(jì)算的，其一般形式如下：

對于問題：一類組合數(shù)學(xué)對象Ω上定義了一個數(shù)值函數(shù)f：Ω→R，研究是否存在某個對象g，其對應(yīng)的數(shù)值函數(shù)的值f（g）≤a或f（g）≥a（a∈R）。先在該類數(shù)學(xué)對象Ω上定義適當(dāng)?shù)母怕誓Ｐ?，則數(shù)值函f數(shù)就轉(zhuǎn)化為概率空間上的隨機(jī)變X計(jì)算其數(shù)學(xué)期望E（X）那么就可以斷言：存在某個對象g，使得：f（g）≤（≥）a。

1.3局部化引理型概率方法

根據(jù)概率論知識，若n個事件A，A，…，A相互獨(dú)立，概率分別是P（1≤i≤n）那么這n個事件同時成立的概率P就是P。但是，事件集的相互獨(dú)立性是很難保證的。退而求其次，在事件集相互依賴性很弱的情況下，也可以估計(jì)該事件集的交事件成立的概率的下界，這就是局部化引理所闡述的內(nèi)容，下面介紹局部化引理在組合數(shù)學(xué)問題中運(yùn)用最為廣泛的一種特殊情形。

局部化引理：若概率空間Ω上的n個事件{Ai|1≤i≤n}滿足以下條件：每個事件的概率都小于p（00（其中A是A的對立事件）。

注：以上定理給出了n個事件都不發(fā)生的概率大于0的一個充分條件。在建立了適當(dāng)?shù)母怕誓Ｐ秃?，運(yùn)用直接型概率方法，結(jié)合局部化引理，就可以判定某個事件發(fā)生的概率是否大于0。

2.概率方法與Ramsey數(shù)的下界估計(jì)

2.1Ramsey數(shù)簡介

考慮命題：6個人中一定有3個人互相認(rèn)識或不認(rèn)識，這個命題對于很多人來說并不陌生，而將這個命題加以推廣就是Ramsey數(shù)的研究內(nèi)容了。

定義：對于正整數(shù)k，l滿足以下條件：任意一個紅藍(lán)邊染色的n階完全圖都有k階紅色完全子圖或l階藍(lán)色子圖的最小正整數(shù)n稱為Ramsey數(shù)，記作R（k，l）。

容易證明，對任意正整數(shù)k，l，Ramsey數(shù)R（k，l）都是存在的，前面的命題是說：R（3，3）≤6。

而對于一般的Ramsey數(shù)R（k，l）， 其值是很難準(zhǔn)確計(jì)算的；退而求其次，可以考慮其下界估計(jì)。下面將運(yùn)用前面提到的三種概率方法給出對稱型Ramsey數(shù)R（k，k）的3種不同的下界估計(jì)。

2.2R（k，k）的3種下界估計(jì)

（1）直接型概率方法

定理：若C2<1，則R（k，k）>n；故∨k≥3，R（k，k）>[2]。

證明： 考慮完全圖K的均勻獨(dú)立隨機(jī)紅藍(lán)邊2-染色，S表示K的某個k階完全子圖，事件A表示S為單色的，則P[A]=2。顯然，K的k階完全子圖有C個，根據(jù)概率的次可加性，K有單色k階完全子圖的概率不大于C2<1，即存在某種染色，使得K無單色k階完全子圖。當(dāng)k≥3時，容易驗(yàn)證：C2<1，故有：R（k，k）>[2]。

（2）期望型概率方法

定理：對于任意正整數(shù)k，n，R（k，k）>n-C2。

證明：考慮完全圖K的均勻獨(dú)立隨機(jī)紅藍(lán)邊2-染色，S表示K的某個k階完全子圖，事件A表示S為單色的，隨機(jī)變量X是S的特征函數(shù)，則X=X表示k階單色完全子圖的數(shù)目。根據(jù)期望的線性性，有：E[X]=E[X]=C2。再根據(jù)期望型概率方法，存在某種染色中，k階單色完全子圖的數(shù)目小于等于C2，再在每一個單色子圖中選取一個頂點(diǎn)去掉，則最多去掉C2個頂點(diǎn)，且最后得出的完全子圖中就沒有單色的k階子圖，從而：R（k，k）>n-C2。

（3）局部化引理型概率方法

定理：若eCC2<1，則R（k，k）>n。

證明：考慮完全圖K的均勻獨(dú)立隨機(jī)紅藍(lán)邊2-染色，S表示K的某個k階完全子圖，事件A表示S為單色的。顯然，每個事件A的概率為p=2，且對不同的k階完全子圖S和S，事件A與A相互不獨(dú)立，當(dāng)且僅當(dāng)S和S有多于2個共同頂點(diǎn)；從而事件集A={A|S為k階完全子圖}中，對每個事件，與其相互依賴的事件數(shù)d0，即存在某種染色，使得K無單色k階完全子圖，從而：R（k，k）>n。

【參考文獻(xiàn)】

[1]李賢平.概率論基礎(chǔ)[M].第三版.北京：高等教育出版社，2010

[2]盧開澄，盧華明.組合數(shù)學(xué)[M].第三版.北京：清華大學(xué)出版社，2002

[3]N.Alon and J.H.Spencer，The Probabilistic Method[M].Third Edition， Wiley，New York，2008

【作者簡介】

王玉梅（1979-），男，漢族，山東濟(jì)寧市人，碩士學(xué)歷，江蘇警官學(xué)院基礎(chǔ)部，講師職稱，主要從事研究方向：應(yīng)用數(shù)學(xué)。