概率方法在Ramsey数理论中的应用

【摘 要】概率方法在组合数学中有很广泛的应用，其中，Ramsey数理论是其中最为经典的例子。本文首先介绍三种组合数学中常用的概率方法，再分别利用这三种方法得出对称型Ramsey数的三种不同下界估计。

【关键词】概率方法；Ramsey数

1.三种基本概率方法

组合数学中常会遇到以下问题：在一个基本的对象空间（一般是有限的）中，具有特定性质的对象是否存在。如果在该对象空间上建立一个古典概型，那么这个问题就转化为：这个特定性质所对应的事件A发生的概率P是否为0；再利用概率论的方法验算概率P是否为零，这就解决问题了。这就是利用概率方法解决组合数学问题的一般思路。根据所运用的概率技巧的不同，概率方法分为很多类，其中最为基本的有三种概率方法：直接型概率方法，期望型概率方法和局部化引理型概率方法。

1.1.直接型概率方法

顾名思义，直接型概率方法就是直接验算事件A的概率P是否为零的方法。其一般思路是：原问题等价于验算的对立事件B的概率是否小于1，再将B转化为若干个事件的并，再分别计算每个事件的概率，利用概率的次可加性，估计B的概率的上界，验算其是否小于1即可。

1.2期望型概率方法

数学期望的线性性决定了其计算的便利，期望型概率方法正是基于数学期望的计算的，其一般形式如下：

对于问题：一类组合数学对象Ω上定义了一个数值函数f：Ω→R，研究是否存在某个对象g，其对应的数值函数的值f（g）≤a或f（g）≥a（a∈R）。先在该类数学对象Ω上定义适当的概率模型，则数值函f数就转化为概率空间上的随机变X计算其数学期望E（X）那么就可以断言：存在某个对象g，使得：f（g）≤（≥）a。

1.3局部化引理型概率方法

根据概率论知识，若n个事件A，A，…，A相互独立，概率分别是P（1≤i≤n）那么这n个事件同时成立的概率P就是P。但是，事件集的相互独立性是很难保证的。退而求其次，在事件集相互依赖性很弱的情况下，也可以估计该事件集的交事件成立的概率的下界，这就是局部化引理所阐述的内容，下面介绍局部化引理在组合数学问题中运用最为广泛的一种特殊情形。

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

注：以上定理给出了n个事件都不发生的概率大于0的一个充分条件。在建立了适当的概率模型后，运用直接型概率方法，结合局部化引理，就可以判定某个事件发生的概率是否大于0。

2.概率方法与Ramsey数的下界估计

2.1Ramsey数简介

考虑命题：6个人中一定有3个人互相认识或不認识，这个命题对于很多人来说并不陌生，而将这个命题加以推广就是Ramsey数的研究内容了。

定义：对于正整数k，l满足以下条件：任意一个红蓝边染色的n阶完全图都有k阶红色完全子图或l阶蓝色子图的最小正整数n称为Ramsey数，记作R（k，l）。

容易证明，对任意正整数k，l，Ramsey数R（k，l）都是存在的，前面的命题是说：R（3，3）≤6。

而对于一般的Ramsey数R（k，l）， 其值是很难准确计算的；退而求其次，可以考虑其下界估计。下面将运用前面提到的三种概率方法给出对称型Ramsey数R（k，k）的3种不同的下界估计。

2.2R（k，k）的3种下界估计

（1）直接型概率方法

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

证明： 考虑完全图K的均匀独立随机红蓝边2-染色，S表示K的某个k阶完全子图，事件A表示S为单色的，则P[A]=2。显然，K的k阶完全子图有C个，根据概率的次可加性，K有单色k阶完全子图的概率不大于C2<1，即存在某种染色，使得K无单色k阶完全子图。当k≥3时，容易验证：C2<1，故有：R（k，k）>[2]。

（2）期望型概率方法

定理：对于任意正整数k，n，R（k，k）>n-C2。

证明：考虑完全图K的均匀独立随机红蓝边2-染色，S表示K的某个k阶完全子图，事件A表示S为单色的，随机变量X是S的特征函数，则X=X表示k阶单色完全子图的数目。根据期望的线性性，有：E[X]=E[X]=C2。再根据期望型概率方法，存在某种染色中，k阶单色完全子图的数目小于等于C2，再在每一个单色子图中选取一个顶点去掉，则最多去掉C2个顶点，且最后得出的完全子图中就没有单色的k阶子图，从而：R（k，k）>n-C2。

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

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

证明：考虑完全图K的均匀独立随机红蓝边2-染色，S表示K的某个k阶完全子图，事件A表示S为单色的。显然，每个事件A的概率为p=2，且对不同的k阶完全子图S和S，事件A与A相互不独立，当且仅当S和S有多于2个共同顶点；从而事件集A={A|S为k阶完全子图}中，对每个事件，与其相互依赖的事件数d0，即存在某种染色，使得K无单色k阶完全子图，从而：R（k，k）>n。

【参考文献】

[1]李贤平.概率论基础[M].第三版.北京：高等教育出版社，2010

[2]卢开澄，卢华明.组合数学[M].第三版.北京：清华大学出版社，2002

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

【作者简介】

王玉梅（1979-），男，汉族，山东济宁市人，硕士学历，江苏警官学院基础部，讲师职称，主要从事研究方向：应用数学。