组合数学中的概率论方法 (1)

组合数学中的概率论方法

概率方法的背景和出发点—

当今科学的发展表明：概率方法是组合数学中最强大和应用广泛的数学工具。导致它迅速发展的一个主要原因在于理论计算机科学与统计物理学中重要研究对象的随机性。概率方法的基本出发点可以描述如下：

为了证明具有某一个组合结构性质的存在性，人们需要构造一个概率空间并且用它证明：在这个空间中随机选取的一个具有此组合性质的元素的概率值为正。

历史上最早运用这个方法的是伟大的数学家P.Erdos ！在过去的五十多年里面他对于这门学问的贡献是如此之大，以至于人们称之为“P.Erdos 方法”。他在这个邻域里面的众多深邃的研究结果不但多如天上的繁星，更因为许多著名的公开问题和猜想而成为这门学科蓬勃发展的发动机。

这个讲义不可能完全介绍这门学科的全貌，它主要是介绍概率方法在组合数学邻域中的运用, 尤其强调通过典型例子的形式来介绍这一方法。

知识背景：

概率是描述事件发生可能性大小的数量指标，它是逐步形成可发展完善起来的。最初人们讨论的是古典概型（随机）试验中事件发生的概率。所谓古典概型试验是指样本空间中的点的样本点的个数是有限的且每一个样本点（组成事件）发生的可能性是相同的，简称为有限性与等可加性。例如：掷一枚均匀骰子的试验与从一个装有n 个相同（编了号）的求中随机模一个球的试验都是古典概型试验。对于古典概型试验，人们给出概率的如下定义：

定义1. 设试验E 是古典概型的，其样本空间Ω由n 个样本点组成，其中一事件A 由r 个样本点组成，则定义事件A 的概率为

，记为 n

P (A ) =

A 中样本点数目r

Ω中样本点数目n

古典概率有下面几个基本性质：

（1）对于任意一个事件A ，有0≤P (A ) ≤1; （2） P (Ω) =1.

（3）设A 1, A 2,..., A m 为互斥的m 个事件，则有

P ( A i ) =∑P (A i )

i =1

m m

注意：在实际应用当中，古典概型受到限制！因为他只用于有限概率空间。而对于无限的情形，则要用到一点定义：

定义2. 设试验E 是的样本空间为某个可以度量的区域Ω，且Ω中任何一个区域出现的可能性大小与该区域的集合度量成正比，而与该区域的位置与形状无关。则称E 为几何概型的试验，且定义事件A 的概率为

P (A ) =

A 几何度量

Ω几何度量

对于几何概型，除了上述(1)-(3)必须满足以外，还要满足下面的无限可加性条件：（4）设A 1, A 2,..., A m ,.... 为两两互斥的无穷多个事件，则

P ( A i ) =∑P (A i ) 。

i =1

∞∞

这个模式提供了一般概率的基本框架。其中包括以下其它性质：（5）P (A ) =1-P (A )

（6）P (B -A ) =P (B ) -P (A ⋂B ) （7）A ⊆B ⇒P (A ) ≤P (B )

（8）对于一般位置上的事件A 1, A 2,..., A m ，有以下的（容斥原理）

P ( A i ) =∑P (A i ) -∑P (A i ) +

i =1

m m m

1≤i

∑P (A A ) -...

j m

... +(-1)

1≤i 1

∑P (A

i 1

A i 2... A i k ) +... +(-1) P (A 1A 2... A m )

这里，求和是对1≤i 1

⎛m ⎫m !

⎪个单项式 =⎪

⎝k ⎭k ! (m -k )!

（9）P (

A ) ≤∑P (A )

i =1

（10）P (

A ) ≤∑P (A )

i =1

∞∞

注意：(9)和（10）称为半可加性。它们是估计概率大小的依据。

随机图定义—我们可以将n 个节点上的所有（带有标号）支撑子图的（K n 的所有支撑子图）全体视为样本空间，记为G n , p （实际上就是有限概率空间(G n , p ) ，p 是一个概率函数。）。

从G n , p 中挑选的一个元素G 被称为一个随机图。

下面是关于随机图的几个例子：

：对于任意G ∈G n , G 的概率志P (G ) 是一个常数2

-N

⎛n ⎫

, N = 2⎪⎪. 。⎝

⎭

2. 依然取G n 如前所定义。取介于0和1之间的任何一个数p 为一个待定的概率函数。我们指定每一条边都具有相同的概率值p ，同时约定：这样的约定是相互独立的。于是，1-p 就是特定一条边没有被选中的概率。对于一个边数为m =e (G ) 的随即图G 而言，它的概率值为

P (G ) =p m (1-p ) N -m

一个值得注意的现象是：p 越小，G 成为以个稀疏图的可能性（概率）就越大！而图论学家的正真兴趣在于：计算或估计一个随机图具有某个特性的概率有多大？下面就是一个关于概率空间G 3, p 的例子：

结论1--G 3, p 中一个随机图连通的概率=3p (1-p ) +p =p (3-2p ) ；结论

2--G 3, p 中一个随机图是二部图的概率=1-p ；

结论3--G 3, p 中一个随机图是二部连通图的概率=3p (1-p ) ；结论4—如果设X 是G 3, p 中元素中联通分支数目，则

232

E (X ) =3(1-p ) 3+2⨯3p (1-p ) 2+1⨯(3p 2(1-p ) +p 3) =3-3p +p 3

设X 是一个非负随机变量而t 是一个正实数。则有

P (X ≥t ) ≤

E (X )

。 t

这个不等式表明：随机变量变大的可能性为零。特别地，

设X n 是一个取值为非负整数的随机变量，它的概率空间为(Ωn , P n ) 。如果

E (X n ) →0当n →∞，那么P (X n =0) →0当n →∞。

这个性质经常被用来证明：对于数值p :0≤p ≤1, 随机图G n , p 几乎具有某种特性。

以下是上述马尔科夫不等式的一个补充。对于随机变量X 和正实数t ，有

P (|X -E (X ) |≥t ) ≤

证明：根据马尔科夫不等式，

V (X )

E ((X -E (X ) ) 2) V (X )

P (|X -E (X ) |≥t ) =P (|X -E (X ) |≥t ) ≤=2

t 2t

这个不等式经常被用于下面的形式：

设X n 是一个取值为非负整数的随机变量，它的概率空间为(Ωn , P n ) ，如果

E (X n ) ≠0且V (X n )

。 P (X n =0) →0（当n →∞）

证明：设X =X n 且t =|E (X n ) |，注意到由于X n =0⇒|X n -E (X n ) |=|E (X n ) |，

P (X n =0) ≤P

(|X n -E (X n ) |≥|E (X n ) |)

一个随机变量X 的平均值就是它的数学期望，定义为：

E (X ) =

X (ω) P (ω) ∑ω

∈Ω

关于数学期望，我们关心它的一些基本性质：（1）

E (∑X i ) =∑E (X i )

（2）E (rX +sY ) =rE (X ) +sE (Y )

（3）如果X A 是一个随机特征变量，那么E (X A ) =P (X A =1) （4）如果E (XY ) =E (X ) E (Y ) ，则称X , Y 是相互独立的随机变量。

(Ω, p ) 里面都有所谓的“随机特征变量”：设A 是概率空间(Ω, p ) 里面的一个事件，关于A 的特征随机变量定义为：

⎧1, ω∈A

∀ω∈Ω⇒X A (ω) =⎨

0, ω∉A ⎩

因此，对于每一个事件都有一个特征随机变量与之对应。反过来，对于一个随机变量X 和

一个实数t ，我们都可以将它与下面事件

{ω∈Ω|X (ω) =t }

下面介绍在实际用应中数学期望的分解技术（即，将一个随机变量X 分解成为若干个具有特殊性质的集合之特征随机变量之和）。由于我们的概率空间一般都是有限的，在计算数学期望时往往要用到组合数学中的一个重要方法---“算两次方法(Double Counting)”. 例如：

X 是定义在概率空间G n , p 上用来计算一个由一些支撑子图组成的集合H 中元素的随机变

量。根据定义，

E (X ) =

G ∈G n , p

∑X (G ) P (G )

是用来计算形如(G , H 0) 的数目的，这里，H 0∈H , 且H 0⊆G . 其中伴随着权函数P (G ). 我们首先根据定义，从外部循环开始，先对于空间G n , p 中的每一个元素（随即图）G ，执行“程序”：在内部循环（H 0∈H ）里面看每一个H 中的元素H 0，如果H 0⊆G ，针对对子(G , H 0) 计算概率P (G ) ；对称地，我们也可以将这个过程反转过来：先从每一个H 中的元素H 0开始，扫描G n , p 中的元素（随即图），如果有支撑子图G ∈G n , p 使得H 0⊆G ，则计算权P (G ) 。这个计算的本质就是计算概率P (H 0⊆G ) 。如果使用特征函数技巧，则有下列分解

E (X ) =

H 0∈H

∑E (X

H 0

)

这里，X H 0是H 0的特征随机函数。上式的本质来自于下面分解

X =

H 0∈H

∑X

H 0

(⇔∀G ∈G n , p , X (G ) =={H 0∈H |H 0⊆G )

H 0∈H

∑X

H 0

(G ) =

H 0∈H H 0⊆G

∑(X

H 0

(G ) =1

下面我们将通过一个实际的应用说明数学期望的分解方法。

例1：设空间G n , p 和自然数k ≥3。我们计算一个随机图G ∈G n , p 中长为k 的圈之数目的均

值。

解答：设X 是G n , p 中每一个随机图G 中含有k -圈的数目的均值（期望），显然，X 是一个定义在G n , p 上，取值于N 中的随机变量。容易看出：G n , p 中k -圈的数目为

(n ) k /2k =

n (n -1)...(n -k +1)

对于每一个k -圈C ，我们可以定义它的特征随机变量为X C :G n , p →{0, 1}使得

⎧1, C ⊆G ;

∀G ∈G n , p ⇒X C (G ) =⎨

⎩0, C ⊄G .

根据定义，P (X C =1) 恰好追踪的是全体G n , p 中这样的元素G ，使得C ⊆G ,

E (X C ) =

由于X =

G ∈G n , p

∑P (G ) X

C (G ) =

G ∈G n , p C ⊆G

∑P (G ) =P (C ⊆G ) =p

。

∑X

E (X ) =∑E (X C ) =

n (n -1)...(n -k +1)

⨯p k

注意：这里P (C ⊆G ) 是事件C ⊆G 的概率，因此，G 不是某个固定元素。有点类似于下面关系

P (X ≥a ) =∑P (x )

x ≥a

粗略地讲，离散数学中的概率方法是沿着下面的想法发展的：为了证明具有某一种特性的对象存在，人们先定义一个足够大的概率空间，然后证明这个空间里面具有这种特性的元素的概率值为正值，下面我们将要证明著名数学家Erdos 早年一个关于大围长和大色数图存在

的定理。Erdos 的这个定理是说：“对于任意大的正整数k ，存在一个图G ，它的围长和色数都大于k 。”首先我们有下面的

准备工作：对于自然数n , k , n ≥k ≥2, 空间G n , p 中的一个元素G 含有一个阶数至少为k 独

立集的概率之多为

k ⎪⎪⎛n ⎫⎝⎭

⎪P (α(G ) ≥k ) ≤ (1-p ) 。 k ⎪⎝⎭

⎛n ⎫

同时还有

k ⎪⎪⎛n ⎫ ⎝⎭

⎪P (ω(G ) ≥k ) ≤ ⎪p ⎝k ⎭

⎛n ⎫

定理（Erdos1959）设有自然数k , l ，那么有图G 使得girth (G ) >l , χ(G ) >k .

证明：固定变量θ

(n ) i i n θi

E (X ) =∑p ≤∑=o (n ) 。

i =32i i =32i

特别地（根据马尔科夫不等式）有

P (X ≥n /2) =o (1) 。

设x =⎡(3/p ) ln n ⎤使得

x ⎪⎪⎛n ⎫-p (x -1) /2⎝⎭

P (α(G ) ≥x ) ≤ x ⎪⎪(1-p )

⎝⎭

⎛n ⎫

()

=o (1)

我们可以选n 充分地大，使得上述两个不等式所涉及事件的概率都小于0.5. 那么存在一个图

G ，其中长度不超过l 的圈的数目少于n /2，同时独立数α(G )

长度不超过l 的圈上拿掉一个节点，得到一个图G *，至少有n /2个节点，同时G *的围长大于l ，且α(G *)≤α(G ). 于是，

|V (G *)|n /2n θ

χ(G *)≥≥=

α(G *)3n 1-l ln n 6ln n

只要我们将n 取得充分大，就一定会有χ(G *)>k . 证毕。

设X , Y 是两个随机变量，我们用

C (X , Y ) =E (XY ) -E (X ) E (Y )

来表示它们的相互关联系数。容易看出，C (X , Y ) =0⇔X , Y 是相互独立的随机变量。作为它们在图论方面的应用，我们可以看看其是怎样使用的。

例2. 设G n , p 是一个随机图，p 是每一条边的概率值。我们用A S 来表示这样一个事件：G [S ]决定一个三角形，其中S ⊆V ，用X S 代表A S 的特征随机变量：

⎧1, ω∈S

X S (ω) =⎨

⎩0, ω∉S

就像以前一样，令

X =∑{X S S ⊆V , |S |=3}

使得X 恰好是图G 中三角形的个数。经过简单计算容易看出：

⎛n ⎫3

E (X ) = 3⎪⎪p

⎝⎭

由于X 是一些形如X S 特征随机变量的和，它的相关系数和方差之间有以下关系：

V (X ) ≤E (X ) +∑C (X S , Y T )

S ≠T

这里，C (X S , Y T ) 的值取决于|S ⋂T |。如果|S ⋂T |≤1, 则C (X S , Y T ) =0; 如果

|S ⋂T |≤2, ，那么G [S ],G [T ]有一条公共边，从而

C (X S , Y T ) =E (X S Y T ) -E (X S ) E (Y T ) =p 5-p 6。

注意到一共有 ⎪⎪(n -2)(n -3) 对这样的(S , T ) 。这样，

⎛n ⎫

⎝2⎭

⎛n ⎫3⎛n ⎫

V (X ) ≤E (X ) +∑C (X S , Y T ) ≤ 3⎪⎪p + 2⎪⎪(n -2)(n -3).

S ≠T ⎝⎭⎝⎭

如果pn →0, 那么V (X ) /E (X ) →0(当n →∞). 根据前面的推论，

P (X =0) →0, 当n →∞时。

这表明：当n →∞时，图G 几乎确定地含有三角形。（注意前提：pn →0, ）。

作为随机变量相关系数的分析的应用，我们来看一下它在图的独立数（有的作者称其为稳定数，stability number of a graph）方面的作用。

G n , p 中的随机图G 几乎含有一个阶数至多为2p -1log n 的独立集（即，当n →∞时，α(G ) ≤2p -1log n ) 。

证明：设G ∈G n , p 而且S 是一个G 中阶数为k +1的节点集合，k ∈N . 那么S 成为一个独立集合的概率为

⎡⎤

(1-p )

⎛k +1⎫

2⎪⎪⎝⎭

。

我们用A S 表示事件：S 是G 中独立集合，且X S 表示事件A S 的特征随机变量。于是乎

E (X S ) =P (X S =1) =P (A S ) =(1-p )

⎛k +1⎫

2⎪⎪⎝⎭

。

设X 为图G 中阶数为k +1的独立集合的数目。则可以将它分解成为下列形式：

X =∑{X S S ⊆V (G ), |S |=k +1}。

故，

⎛n ⎫⎝

⎪E (X ) = (1-p ) k +1⎪⎝⎭

⎛k +1⎫

⎪2⎪⎭

。

应用不等式

⎛n ⎫n k +1-p

k +1⎪⎪≤(k +1)! , 1-p ≤e ⎝⎭

直接可以得到

⎛k +1⎫

-p 2⎪⎪k +1⎝⎭

n e

E (X ) ≤

(k +1)!

(ne =

-pk /2k +1

)

(k +1)!

-pk /2

。

如果我们取k =2p -1log n ，则k ≥2p log n , 且ne

⎡⎤

-1

≤1。由于k 的增长速度至少比

log n 快，上式表明：当n →∞时，E (X ) →0. 由于X 是取值于非负整数的随机变量，作

为前面推论的直接结果，

P (X =0) →1

当n →∞。从而，一个G n , p 中的随机图几乎确定有阶数至多是k 的独立集合。下面我们将推出一个属于Bollobas 和Erdos （1976）和Mtula(1976)的一个结果。

k ⎪⎪⎛n ⎫- *⎝⎭⎪2k 定理。设G ∈G 1, 对于0≤k ≤n , 设函数f (k ) = ，而且是使得f (k )

⎝⎭2

⎛n ⎫

的最小的数值k 。那么几乎所有的独立数α(G ) 都取值于{k *-2, k *-1, k *}。

证明：设X S 是事件A S :（∀S ⊆V ⇒S 是G 的一个独立集合）的特征随机变量。我们将随机变量X 进行如下分解：

X =∑{X S S ⊆V , |S |=k }且E (X ) =f (k ).

注意：这是可以做到的（如前面准备工作1的证明所述）。同样如前面分析可知：几乎保证有α(G ) ≤k *。这样，根据Chebyshef 定理后面的的推论，我们只需要证明：当k =k *-2 时必有V (X )

准备工作2. k

|S ⋂T |≤1⇒C (X S , X T ) =0。

如果|S ⋂T |=i , 2≤i ≤k -1，则

C (X S , X T ) ≤E (X S X T ) =P (A S ⋂A T ) =2

⎛i ⎫⎛k ⎫

2⎪⎪-2 ⎪⎪⎝⎭⎝2⎭

。

注意：这个概率是这样得到的：事件A S ⋂A T 表明S , T 这两个集合同时都是独立集合。

⎛k ⎫- 2⎪⎪⎝⎭

这样，P (A S ) =2

⎛1⎫= ⎪⎝2⎭

⎛k ⎫ 2⎪⎪⎝⎭

（S 中任何两个节点决定的边不在G [S ]中，一共有 ⎪⎪个

⎛k ⎫

⎝2⎭

对子）；同时，T -S 中的点对之间没有边；T -S 与S ⋂T 之间的点对没有边，于是乎

⎛1⎫

P (A S ⋂A T ) = ⎪

⎝2⎭

⎛k ⎫ 2⎪⎪⎝⎭

⎛1⎫ ⎪⎝2⎭

⎛k -i ⎫ 2⎪⎪⎝⎭

⎛1⎫

⎪⎝2⎭

i (k -i )

⎛i ⎫⎛k ⎫ 2⎪⎪-2 ⎪⎪⎝⎭⎝2⎭

⎛1⎫= ⎪⎝2⎭

⎛k ⎫⎛i ⎫2 2⎪⎪- ⎪⎪⎝⎭⎝2⎭

也许，这可以另外解释如下：

⎛1⎫

P (A S ⋂A T ) =P (A S ) P (A T ) /P (A S ⋂T ) = ⎪

⎝2⎭

实际上是一种容斥原理，反应在指数运算上。

⎛|S |⎫⎛|T |⎫⎛|S ⋂T |⎫ ⎪ 2⎪⎪+ ⎪⎪- ⎪⎝⎭⎝2⎭⎝2⎭

⎛1⎫= ⎪⎝2⎭

⎛k ⎫⎛i ⎫2 2⎪⎪- ⎪⎪⎝⎭⎝2⎭

从统计意义上看，有 k ⎪⎪种方式选S ，对于每一个选定的S ，一共有 i ⎪⎪种方式选S ⋂T ；

⎝⎭⎝⎭

⎛n ⎫⎛k ⎫

最后，对于选定的S ，一共有 k -i ⎪⎪种方式选T ；这样，根据前面得到的不等式，

⎝⎭

2⎪⎪-2 ⎪⎪⎛n ⎫⎛k ⎫⎛n -k ⎫

⎝⎭⎝2⎭

V (X ) ≤E (X ) +∑C (X S , Y T ) ≤E (X ) +∑ k ⎪⎪ i ⎪⎪ k -i ⎪⎪2

S ≠T i =2⎝⎭⎝⎭⎝⎭

k -1

⎛i ⎫

⎛k ⎫

⎛n -k ⎫

由于E (X ) = ⎪⎪ ⎪

⎛n ⎫⎛1⎫

⎝k ⎭⎝2⎭

⎛k ⎫ 2⎪⎪⎝⎭

⎛i ⎫

⎛k ⎫

2⎪⎪-2 ⎪⎪ 2⎪⎪⎛n ⎫⎛k ⎫⎛n -k ⎫ ⎛n ⎫-2 2⎝⎭⎝2⎭⎝⎭

或者等价于证明

⎛n ⎫

k ⎪⎪⎝⎭

这里

-1

∑g (i ) →0(n →∞) （*）

i =2

k -1

2⎪⎪⎛k ⎫⎛n -k ⎫ ⎝⎭

⎪ ⎪g (i ) = ⎪ ⎪2. i k -i ⎝⎭⎝⎭

⎛i ⎫

首先，我们有

⎛k ⎫⎛n -k ⎫2⎛n ⎫⎪ ⎪ g (2) =2

且对于2≤i ≤k -2,

⎛2i ⎫⎛k 2⎫g (i +1) (k -i ) 22i k 22i

⎪ ⎪ =

设t =⎣c log 2n ⎦，0

g (i +1) ⎛2i ⎫⎛k 2⎫⎛2t

⎪ ⎪

4n c log 2n =≤1c (n -4log 2n )

从而

⎫⎛k 2⎫⎛n c ⎫⎛(2log 2n ) 2⎫⎪⎪ n -2k ⎪⎪

⎛n ⎫

k ⎪⎪⎝⎭

下面分析余下部分：

-1

⎛n ⎫tk 4

g (i )

-1

⎛k ⎫⎛n -k ⎫-(k -i )(k +i -1) /2⎛i ⎫⎛k ⎫

2⎪⎪ 2⎪⎪k -1 ⎛k ⎫⎛n -k ⎫ k -i ⎪⎪ k -i ⎪⎪2⎝⎭⎝⎭

⎪ ⎪g (i ) =2=2∑∑ ⎪ ⎪∑⎝⎭⎝⎭

i =t +1i =t +1⎝i ⎭⎝k -i ⎭i =t +1

k -1

⎛k ⎫ 2⎪⎪k -t -1⎝⎭

⎛k ⎫⎛n -k ⎫-j (2k -j -1) /2 ∑ j ⎪⎪ j ⎪⎪2j =1⎝⎭⎝⎭

-(k +t /2) j

⎛k ⎫ 2⎪⎪k -t -1⎝⎭

j =1

∑(k (n -k ) 2

)

准备工作3. k *+log 2k *-1≥2log 2n 因此有

2-k /2

对于充分大的自然数n ，

k (n -k ) 2-(k +t ) /2

从而有

i =t +1

∑g (i )

-1

⎛k ⎫

k -1

⎛k ⎫ 2⎪⎪⎝⎭

(k -t -1)

使用这个上界，我们得到

⎛n ⎫ k ⎪⎪⎝⎭

-1

2⎪⎪⎛n ⎫ k -t -1⎝⎭

⎪g (i )

这样，极限（**）和（***）可以导出极限（*）. 最后外耳门可以得到

V (X ) /E 2(X ) →0(n →∞)

由Chebyshef 不等式及其推论，定理证毕。

例3（交叉数引理，Ajtai 1982,Leighton 1983）设G 是一个简单图且边数m 和点数n 满足条件：m ≥4n 。那么

m 3

Cr (G ) ≥

64n 2

证明（N.Alon&Spencer2000）我们考虑G 的一个平面最优画法G ，它加号有Cr (G ) 个交叉数。设S 是节点集合V (G ) 的一个随机子集合，每一个节点的概率为p =4n /m ，且

H =G [S ],且H =G [S ]。我们定义Ω上的随机变量如下：

X -节点数；Y -边数；Z -边与边的交叉数目

一个显而易见的事实是：

Z ≥Cr (H ) ≥Y -3X ⇒E (Z ) ≥Cr (H ) ≥E (Y ) -3E (X ) 因为

E (X ) =pn , E (Y ) =p 2m (每一边有两个端点),

E (Z ) =p Cr (G （每一个交叉数由) 4个点决定。）

从而有

pm -3n m 3

p Cr (G ) ≥p m -3pm ⇒Cr (G ) ≥=32

p 64n

点评：Sz e kely 在1997年发觉到上述交叉数引理在组合几何学方面会有应用，由它可以轻

松地推出一些著名的结果来。下面我们介绍它在组合几何方面的两个应用。

设有平面上n 个点。任何两个点可以决定一条直线。问题是：可能会有三个点位于同样一条直线上。特别地，给定自然数k ，人们可以发问：到底有多少条直线通过n 个点中的至少某

k 个点？例如：对于完全平方数n ，这n 个点都位于一些正方形的格点上，那么有2n +2

条直线通过其中的某些n 个点。这个界是否可以改进？下面的Szemeredi 和Trotter 的结果

对于一般的自然数k 提供了下界。

应用1（Szemeredi&Trotter1983）设平面上n 个点的集合为P ，且l 是通过其中k +1个点的

n 2

直线数目，1≤k ≤2n 。则l

解答：我们可以以P 中的点形成一个图G 的节点集合，它的边是由通过至少k +1个点的直线上连续分布的G 中的点之间的线段组成。那么G 至少有kl 条边，且它的交叉数至少为

⎛l ⎫23

⎝⎭

⎛l ⎫n 232

l /2> 2⎪⎪≥Cr (G ) ≥(kl ) /64n 。无论何种情况发生，都有l

⎝⎭

下面第二个应用来自Spencer(1984).

应用2. 设P 是平面上n 个点的集合，k 是其中距离为1的点对个数。那么k

1n -1

圆的个数：它们恰好通过P 的i 个点。于是有n =∑n i ，设k =∑in i . 现在可以做一个

2i =0i =0

n -1

图H 下：V (H ) =P , 它的边由通过至少三点的圆上相邻的圆弧决定。于是有

e (H ) =∑in i =2k -n 1-2n 2≥2k -2n

i =0

n -1

注意到H 可能为重图，去掉重复的边得到一个简单图G , e (G ) ≥k -n 。由于G 是从至多n 圆得到，而且任意两个圆至多有2个公共点。于是，当e (G )

n >n (n -1) ≥Cr (G ) ≥(k -n ) /64n (交叉数引理) ，从而k

下面将要介绍一个组合学方面的重要定理—The Erdos-Ko-Rado Theorem。

首先我们需要一些准备工作。一个集合族F 称为相交族，如果它满足下列条件：

232

∀A , B ∈F ⇒A ⋂B ≠φ.

设F 是某个n 元集合{0, 1, 2,..., n -1}的一些k -子集合形成的相交集合族，n ≥2k . The

Erdos-Ko-Rado 定理说明：|F |≤ k -1⎪⎪. 我们提供一个由Katona 在1972年发现的证明。

⎝⎭引理1. 对于0≤s ≤n -1, 定义集合A s ={s , s +1,..., s +k -1},这里的加法都取mod n. 则如

⎛n -1⎫

上所述的相交集合族F 至多含有k 个这样的A s 。

证明：选定某个A s ∈F . 。所有其它的A t ，如果A s ⋂A t ≠φ，我们可以将这样的A t 分成一对一对的形如{A s -i , A s +k -i },(1≤i ≤k -1) 。容易看出，这样的每一对中的集合都是不相交的。根据F 的定义，F 至多只能含有每一对中的一个！证毕

点评：其实这个结论很明显。

我们现在来证明The Erdos-Ko-Rado Theorem 。取一个{0, 1, 2,..., n -1}上的置换σ，同时随机地，一致地，而且是独立地取元素i ∈{0, 1, 2,..., n -1}，可以形成一个集合

A ={σ(i ), σ(i +1),..., σ(i +k -1)},

其中的加法运算还是模n 运算。上述引理表明：

P (A ∈F ) ≤

k n

但由于上述集合A 是从所有k -子集合里面一致地选取，

k |F |

≥P (A ∈F ) =

n ⎛n ⎫

k ⎪⎪⎝⎭

从而有

k ⎛n ⎫⎛n -1⎫

⎪⎪。 |F |≤ = ⎪ n ⎝k ⎭⎝k -1⎪⎭

证毕。

下面我们介绍概率方法在证明Sperner 定理方面的应用。

集合{1, 2, 3,..., n }的一些子集合形成的族F 被成为一个反链，如果F 中的任何两个元素之间都不存在相互包含关系。

定理1. 设F 是一个反链，则有

≤1 ∑n ⎫A ∈F ⎛ |A |⎪⎪⎝⎭

证明：一致地选取{1, 2, 3,..., n }上的一个置换σ，令

C σ={{σ(j ) |1≤j ≤i }0≤i ≤n }。

这里，两个极端情形：i =0时φ∈C σ; i =n 时{1, 2,..., n }∈C σ。定义一个随机变量

X =F ⋂C σ。

我们将上述随机变量进行分解如下：

X =∑X A 。

A ∈F

其中X A 是关于事件A ∈C σ的特征随机变量。由于C σ中仅有一个阶数为|A |的集合，而它在所有|A |-子集合中是一致地分部的，于是，

E (X A ) =P [A ∈C σ]=

。 n ⎛⎫ |A |⎪⎪⎝⎭

根据数学期望的线性性，

E (X ) =

∑n ⎛⎫A ∈F

|A |⎪⎪⎝⎭

另外一方面，对于任何一个σ，C σ本身就是一个链---其中任何两个元素之间存在包含关系。而F 是一个反链，必须有X =|F ⋂C σ|≤1. 从而E (X ) ≤1。证毕。推论（Sperner ’s Theorem）如果F 是一个反链，则有

⎛n ⎫

|F |≤ n /2⎪⎪。

⎦⎭⎝⎣

⎛n ⎫

证明：注意到函数 x ⎪⎪在x =⎣n /2⎦达到最大，有

⎝⎭

1≥

1|F |

≥∑⎛n ⎫A ⋃F ⎛n ⎫

⎪ |A |⎪ n /2⎪

⎦⎪⎝⎭⎝⎣⎭

下面我们来介绍数学分析里面的的一个关于函数逼近的定理-Weierstrass 逼近定理的一个概率证明（这个证明属于Benrstein 在1912年发现的）

定理（Weierstrass 逼近定理）对于区间[0,1]上的任何一个联讯的实函数f :[0, 1]→R 以及

任意的实数ε>0, 存在一个实系数多项式p (x ) 使得对于任何实数x ∈[0, 1]，都有

f (x ) -p (x ) ≤ε

证明：我们知道，一个比区间上的连续函数一定是一致连续的（即，对于任意整数

ε>0, ∃σ>0, s . t .(∀x ' , x " ∈[a , b ],|x ' -x " |≤σ⇒|f (x ' ) -f (x " ) |

函数还是有界的（即，存在整数M >0, s . t . ∀x ∈[a , b ]⇒|f (x ) |≤M ）

设B (n , x ) 是以x 为概率的n 重贝努力实验中事件A 恰好发生的概率，则其中事件A 恰好发

k n -k k n -k

⎪ ⎪生k 的概率为：（）。则B (n , x ) 的数x (1-x ) B (n , x ) =k 的概率为x (1-x ) ⎪ ⎪

⎛n ⎫⎝k ⎭⎛n ⎫⎝k ⎭

学期望为nx 而它的标准方差为nx (1-x ) ≤个自然数n ，

n 。这样，根据Chebyshef 不等式，对于每一

⎡⎤13

P ⎢B (n , x ) -nx >n ⎥

从而有自然数n 使得同时有

⎡⎤ε13

P ⎢B (n , x ) -nx >n ⎥

成立。

定义函数

⎛n ⎫i n -i ⎛i ⎫⎪p n (x ) =∑ x (1-x ) f ⎪。 i ⎪

⎝n ⎭i =0⎝⎭

下面证明这个函数为所求。

我们考虑

p n (x ) -f (x ) =

⎛n ⎫i n -i ⎪(f (i /n )-f (x ) )x (1-x ) ∑ i ⎪i =0⎝⎭

∑

i :i -nx ≤n

⎛n ⎫i n -i ⎪(f (i /n ) -f (x ) )+x (1-x ) ⎪2

⎝i ⎭3

∑

i :i -xn >n

⎛n ⎫i n -i

⎪(f (i /n )-f (x ) )x (1-x ) ⎪2

⎝i ⎭3

≤

∑

i :|i -xn |≤n

⎛n ⎫i n -i

⎪x (1-x ) f (i /n ) -f (x ) + ⎪2

⎝i ⎭3

∑

i :|i -xn |>n

⎛n ⎫i n -i

⎪x (1-x ) |f (i /n ) -f (x ) | ⎪2

⎝i ⎭3

⎛n ⎫i n -i

⎪x (1-x ) |f (i /n ) -f (x ) | i ⎪⎝⎭

≤

∑

i :|i /n -x |≤

⎛n ⎫i n -i ⎪x (1-x ) |f (i /n ) -f (x ) |+∑ i ⎪

1⎝⎭i :|i /n -x |>

n 3n 3

≤

+2M ⨯

=ε

这里，

i 1i :-x >n

n 3

⎛n ⎫i n -i ⎪x (1-x ) f (i /n ) -f (x ) ≤P [|B (n , x ) -nx |]⨯2M i ⎪⎝⎭

证毕。

一个有向完全图被称为一个竞赛图，这个概念来自于体育比赛。如果一次体育比赛规定：每两个选手x , y 必须比赛一次，如果前者打败了后者，那么用一条从x 到y 的有向边(x , y ) 表示其胜负关系，这样就自然地形成了一个竞赛图。这样的结构往往使用在大型体育竞标赛的

第一阶段。关于竞赛图，Sch u tte 提出了所谓的“局部王者”的概念，即，对于竞赛图中的任何一个k -集合A k ，存在一个节点x k , 它可以击败A k 中的所有选手。如果一个竞赛图具有上述结构，我们就称其为具有性质S k 。Sch u tte 本人提出下列问题：

对于自然数k ，一个竞赛图T =(V , E ) 满足什么条件时满足性质S k

对于较小的自然数，可以发现这样的性质。例如：我们选一个竞赛图T =(V , E ) 为三个节点的竞赛图，它的有向边为E ={(1, 2), (2, 3), (3, 1)}。容易看出：这个竞赛图满足S 1。对于一般的S k ，Erdos 在1963年发现它很简单的问题，如果允许使用概率方法的话。下面这个结果属于Erdos ，它表明：对于任何自然数k ，只要完全图的阶数自然数n 充分地大，那么一定会有一个定向，使得相应的竞赛图满足性质S k 。

例4：对于任何自然数k ，只要自然数n 地大，那么一定有一个n 阶竞赛图满足性质S k 。具

-k

⎪体地讲，只要 1-2 ⎪

⎛n ⎫⎝k ⎭

()

n -k

解答：我们使用概率方法。首先要定义一个随机竞赛图的概念。一个节点集合V ={1, 2,.., n }上的竞赛图是所谓随机的，如果对于每一对数i , j ，选择边(i , j ) 和(j , i ) 的概率完全相同，

⎛n ⎫

2⎪⎪⎝⎭

都是1/2.这样，V ={1, 2,.., n }上的竞赛图一共有2

个。如此以来，概率空间变得完全对

称，对于这样的空间里面的元素，我们称其为随机元素，不谈其概率法分部。

考虑V ={1, 2,.., n }上的一个随机竞赛图T 。对于任何一个k -子集K ，我们用A K 表示事件：

T 中没有节点可以击败K 中的所有元素。则有

P (A K ) =1-2-k

()

n -k

-k

这是因为，每一个V -K 中的节点v 不能击败所有K 中元素的概率是1-2。于是有

⎛⎫ ⎪⎛n ⎫-k P A K ⎪≤∑P (A K ) = k ⎪⎪1-2

⊆V ⎝⎭ K ⊆V ⎪|K

⎝|K |=k ⎭K |=k

()

n -k

这表明：存在一个竞赛图里面的一个元素可以击败它的每一个k -子集K 中的元素，即，有

一个竞赛图满足性质S k 。

注：关于性质S k ，我们用f (k ) 表示一个竞赛图满足S k 时的最小阶数。那么有

c 12k k ≤f (k ) ≤k 22k (ln2)(1+o (1))

下面我们来看一个极值图论问题。

问题：设G =(T , B , E ) 是一个二部图，它的边连接两个部集T , B 。如果G 没有4-圈，那么

它的边数最多是多少？

点评：这个问题在一般图中的平行问题是：一个n 阶图G 中如果没有3-圈，那么它的边数最多是多少？

⎡n 2⎤

关于这个问题的答案是：在不含有3-圈的前提下，一个n 阶图G 的边数最大值是⎢⎥。而

⎣4⎦⎡n 2⎤

且达到⎢⎥的充分必要条件是G =K ⎡n ⎤⎡n ⎤。这可以直接用组合计数方法得到。

⎢2⎥, ⎢2⎥⎣4⎦⎣⎦⎢⎥

这个问题的另外一个平行问题是：一个n 阶图G 中如果没有4-圈，那么它的边数最多是多

少？

关于这个问题的答案是：一个n 阶图G 中如果没有4-圈，那么它的边数最多是

n (1+4n -3) 。 4

它是在1958年由I.Reiman 证明的。如果要用简单的方法来证明，可以直接使用“算两次”的方法。这是一个十分典型的高中数学竞赛问题。作为极值图论的一个部分，早年人们只是将它作为一个数学游戏来玩，一直没有发现它的实际用途。直到2010年华东师范大学数学系的任韩先生在研究图中的短圈分部时发现这个结果在分析图中的短圈分部时非常有用。事实上我们可以用它证明以下结果：

一个n 阶简单图中3-圈和4-圈的数目分别为O (n 3) 和O (n 4) ，这写界都是最好可能的，而且存在多项式算法发现所有最短圈（即使图中没有3-圈或4-圈）。

让我们回到原来的问题上。设边数为m =n +n +1。于是有一个阶为n 和m 个点的投影平面（Fano plane）P 。我们T 的节点视为P 中的点（point ），B 中节点视为其中的直线线段（line ）。于是可以定义一个新的图G =G P 如下：

∀t ∈T , ∀b ∈B , (t , b ) ∈E (G P ) ⇔t 位于b 上。

由于两个点不可能位于两条直线段上，G P 中没有4-圈。注意：如此构造出来的图G P 有如下性质：（1）|T |=|B |=m ;

（2）每一个T 中的点的度为n +1（每一个P 中的点恰好位于n +1个直线上）；（3）每一个B 中的点的度为n +1（每一个P 中的直线恰好含有n +1个点）；

结论—这样的一个G P 具有最多可能的边（即，在所有不含4-圈的图中G P 的边数最多），同

时，任何一个能够达到这个边数的不含4-圈的图都可以表示成一个G =G P 的形式。

假定G 是一个一般的不含有4-圈的图。设b 1, b 2∈B 是均匀挑选出来的一对不同元素。对于

t ∈T , 用d (t ) =|D (t ) |表示B 中与t 关联的元素数目。让I t 表示一个特征随机变量，用以刻

画t 与b 1, b 2的关联关系。那么有

⎛d (t ) ⎫⎛m ⎫

E [I t ]=Pr[b 1, b 2∈D (t )]= 2⎪⎪/ 2⎪⎪。

⎝⎭⎝⎭

现在令

X =∑I t ，

t ∈T

则它就是同时与b 1, b 2有关联关系的T 中元素t 的总数。根据条件，X ≤1（这等价于G 中没有4-圈）。利用数学期望的线性性，

⎛d (t ) ⎫⎛m ⎫

E [X ]=∑E [I t ]=∑ 2⎪⎪/ 2⎪⎪

t ∈T t ∈T ⎝⎭⎝⎭

⎛y ⎫

用d =m ∑d (t ) 表示图中节点的平均度数。根据函数 2⎪⎪的凸性，

t ∈T ⎝⎭

-1

⎛d (t ) ⎫⎛m ⎫⎛d ⎫⎛m ⎫

⎪ ⎪ /≥m ∑ 2⎪ 2⎪ 2⎪⎪/ 2⎪⎪， t ∈T ⎝⎭⎝⎭⎝⎭⎝⎭

注意：当等式成立时，由于B 处于和T 对偶的地位，所有b ∈B 均有相同的度。从而对应

的图是正则图。现在

⎛d ⎫⎛m ⎫1≥max X ≥E [X ]≥m 2⎪⎪/ 2⎪⎪. ⎝⎭⎝⎭

这就是一个二部图不含有4-圈的必要条件。我们先来考虑G =G P （说明它可以使得等式成立），它的每一个T 中的点x 具有相同的度d (x ) =d （每一个直线上有n +1个点）。这样，X ≡1（任何两个点决定唯一的直线）。于是，所有的不等式都是等式：

⎛d ⎫⎛m ⎫1=m 2⎪⎪/ 2⎪⎪. ⎝⎭⎝⎭

如果一个图含有更多的边，那么它的节点的平均度数将会严格大于d =m -1∑d (t ) ，从而

t ∈T

会有1

假定一个二部图G =(T , B , E ) 含有和G P 一样多的边，同时不含有4-圈。重复前面使用过的讨论，由于最后一个不等式成为等式，前面得到的一系列不等式都成为等式。于是总有X =1. 定义一个投影几何(Fano geometry) ，它以T 为点（points ）的集合，选取直线为每一个b ∈B 的邻域N (b ) 。由于X =1，任何两个点决定唯一一个直线。如果把T , B 的角色互换（可以知道对于任何一个G 中节点的度都相同，为n +1, ），我们可以得知：任何两条直线决定为一个点（point ）。这样一来，G =(T , B , E ) 就是从一个投影平面(Fano plane)生成。 ⎛d ⎫⎛m ⎫

组合数学中的概率论方法 (1)

相关内容

热门内容