组合数学之概率法

概率法

1 The Probabilistic Method

概率法的两种基本方法:

• 对于概率空间$\Omega$和事件$P$, 如果$\Pr_x[P(x)]>0 =>\exists x\in\Omega$ 满足性质$P$.
• 对于随机变量$X$, 存在$x\le \mathbb E[X]$, $X=x$; 也存在$x\ge \mathbb E[X]$, $X=x$.(存在大于等于期望的, 也存在小于等于期望的.)

1.1 Ramsey number

无论如何边着色(2色), $K_6$中一定有单色$K_3$(边颜色相同的三角形).
推广:
罗素数$R(k,l)$是最小的整数$n$满足对于$K_n$的任意二着色, 要么有红色的$K_k$, 要么有蓝色的$K_t$.

Ramsey’s(罗素) Theorem
如果$n\ge R(k,k)$, 对于$K_n$的任意二色边着色, 一定有单色的$K_k$.

$R(k,l)$很难算, 但是我们可以给出$R(k,k)$的下界.

Theorem (Erdős 1947)
如果$\binom{n}{k}\cdot 2^{1-\binom{k}{2}}<1$, 那么存在$K_n$的二着色满足没有单色子图$K_k$.

证明:
构造$K_n$的随机着色: 每条边独立以$1/2$概率决定颜色.
对于任意$k$点集合$S$, $\epsilon_S$表示$S$诱导的$K_k$子图是单色的. $K_k$中有$\binom{k}{2}$条边, 所以

$$\Pr[\epsilon_S]=2\cdot2^{-\binom{k}{2}}=2^{1-\binom{k}{2}}$$

又因为$S$的选取有$\binom{n}{k}$种, 因为union bound,

$$\Pr[\exists S,\epsilon_S]\le \binom{n}{k}\cdot \Pr[\epsilon_S]=\binom{n}{k}2^{1-\binom{k}{2}}$$

根据假设, $\binom{n}{k}\cdot 2^{1-\binom{k}{2}}<1$, 所以存在一种二着色, 没有一个$\epsilon_s$发生, 也就是没有单色$k_k$子图. 根据上述结论, $k\ge 3$时选取$n="\lfloor" 2^{k 2}\rfloor$, $\binom{n}{k}\cdot 2^{1-\binom{k}{2}}<1$就满足, 因此对于任意$k\ge 3$有$r(k,k)>n=\lfloor 2^{k/2}\rfloor$.

1.2 Tournament

竞赛图Tournament指完全图的一个定向. 对于任意两个不同的点$u,v$, 要么有$(u,v)\in E$, 要么有$(v,u)\in E$, 不可能两者都有.
$k$-paradoxical: 一个竞赛图是$k$-paradoxical的当且仅当对于任意$k$个参赛者, 都存在一个参赛者赢了他们全部

Theorem(Erdős 1963)
如果$\binom{n}{k}(1-2^{-k})^{n-k}<1$, 则存在一个$k$-paradoxical的$n$点竞赛图.

证明:
考虑均匀随机的$V=[n]$上的竞赛图$T$, 对于每个固定的$k$-子集$S\in\binom{V}{k}$, 定义事件$A_S$: $V\setminus S$中不存在顶点打赢了$S$中所有顶点.
在一个均匀随机竞赛图中, 每条边的定向是独立随机的. 对于任意$u\in V\setminus S$,

$$\Pr[u\text{ beats all }v\in S]=2^{-k}$$

所以$\Pr[u\text{ does not beat all }v\in S]=1-2^{-k}$,

$$\Pr[A_s]=\prod_{u\in V\setminus S}\Pr[u\text{ does not beat all }v\in S]=(1-2^{-k})^{n-k}$$

所以

$$\Pr[\lor_{S\in\binom{V}{k}}A_S]\le \sum_{S\in\binom{V}{k}}\Pr[A_S]=\binom{n}{k}(1-2^{-k})^{n-k}<1$$

所以

$$\Pr[T\text{ is k-paradoxical}]=\Pr[\land_{S\in\binom{V}{k}}\overline{A_s}]=1-\Pr[\lor_{S\in\binom{V}{k}}A_S]>0$$

1.3 Hamiltonian paths

Theorem(Szele 1943)
存在有至少$n!2^{-(n-1)}$条哈密顿路径的$n$点竞赛图.

证明:
考虑$[n]$上的均匀随机竞赛图$T$. 对于任意$[n]$的排列$\pi$, 定义$X_\pi$为指示随机变量

$$X_\pi= \begin{cases} 1, &\forall i\in[n-1],(\pi_i,\pi_{i+1})\in T,\\ 0, &otherwise. \end{cases}$$

即$X_\pi$指示了$\pi_0\to\pi_1\to\cdots\to\pi_{n-1}$是否是哈密顿路径.

$$\mathbb E[X_\pi]=\Pr[X_\pi=1]=\Pr[\forall i\in[n-1],(\pi_i,\pi_{i+1})\in T]=2^{-(n-1)}$$

令$X=\sum_{\pi:\text{permutation of }[n]}X_\pi$表示$T$中总的哈密顿路径的数量.

$$\mathbb E[X]=\sum_\pi\mathbb E[X_\pi]=n!2^{-(n-1)}$$

为哈密顿路径数量的平均数, 所以肯定存在一个$n$点竞赛图, 哈密顿路径大于等于该值.

1.4 Independent sets

独立集: 任意两点之间没有边的顶点集合.(不相邻)

Theorem
$G(V,E)$表示$n$点$m$边的图. 则$G$有大小至少为$\frac{n^2}{4m}$的独立集.

1. 随机采样出集合$S$: 每个点独立地以概率$p$被选择.
2. 将$S$改为独立集$S’$: $\forall uv\in E$, 如果$u,v\in S$, 从$S$中删除$u,v$之一.
   显然$\mathbb E[|S|]=np$.
   对于每条边$e=uv\in E$, $Y_e$为指示是否$uv$都在$S$中的随机变量. 则 $$\mathbb E[Y_{uv}]=\Pr[u\in S\land v\in S]=p^2$$ 令$Y$为$G$中被$S$诱导的边的数量, 则$Y=\sum_{e\in E}Y_e$. 根据期望的线性: $$\mathbb E[Y]=\sum_{e\in E}\mathbb E[Y_e]=mp^2$$ 因为$G(S)$中有$Y$条边, 所以从$S$到$S’$至多删除了$Y$条边, 即$|S^*|\ge |S|-Y$. 所以 $$\mathbb E[|S^*|]\ge \mathbb E[|S|-Y]= \mathbb E[|S|]- \mathbb E[Y]=np-mp^2\ge \frac{n^2}{4m}$$ 最后是因为当$p=\frac{n}{2m}$, 期望最大.
   因此存在大小至少为$\frac{n^2}{4m}$的点独立集.

方法2:
首先构造一个$[n]$的排列$\pi$, 根据$\pi$构造独立集S: 按照顺序选, 只要邻居还没选, 就选进去.

$$\mathbb E[|S|]=\sum_{v\in V}Pr[v\in S]=\sum_{v\in V}\frac{1}{deg(v)+1}\ge \frac{n^2}{2m+n}$$

其中第二步是因为一个点被选入$S$当且仅当在$\pi$中它比所有邻居都早出现. 最后一步使用了柯西不等式, 注意$\sum_v{deg(v)+1}=2m+n$

1.5 Coloring large-girth graphs

围长(girth)$g(G)$: 图$G$中最小长度的环的长度
着色数$\chi$: 将图properly着色(相邻点不同色)的最少颜色数量

Theorem(Erdős 1959)
对于任意$k,l$, 存在有限图$G$, $\chi(G)\ge k$且$g(G)\ge l$

着色类: 同色顶点的等价类, 为独立集.
独立数$\alpha(G)$: 图$G$中最大的点独立集的大小.

Lemma
对于任意$n$点图$G$, 有$\chi(G)\ge \frac{n}{\alpha(G)}$

因为$n$个点要分成$\chi(G)$个着色类, 每个着色类都是点独立集, 根据鸽笼原理, 至少有一个着色类(独立集)的大小至少为$n/\chi(G)$. 因此$\alpha(G)\le n/k=>\chi(G)\ge k$.
所以我们只需要证明存在图$G$满足$\alpha(G)\le n/k$且$g(G)>l$.

首先保证$\Pr[X\ge\frac{n}{2}]=o(1)$

固定$\theta<1/l$. 令$G$为$G(n,p)$($K_n$中每条边以概率$p$被选), $p=n^{\theta-1}$. 对于任意长度为$i$的简单环$\sigma$, 令$X_\sigma$为指示随机变量

$$X_\sigma=\begin{cases} 1 & \sigma\text{ is a cycle in }G\\ 0 & \text{otherwise.} \end{cases}$$

则$G$中长度至多为$l$的环的数量为

$$X=\sum_{i=3}^l\sum_{\sigma:i-cycle}X_\sigma$$

对于长度为$i$的简单环$\sigma$,

$$\mathbb E[X_\sigma]=\Pr[X_\sigma=1]=\Pr[\sigma\text{ is a cycle in }G]=p^i=n^{\theta i-i}$$

对于任意$3\le i\le n$, 长度为$i$的简单环的数量为$\frac{n(n-1)\cdots(n-i+1)}{2i}$.

$$\mathbb E[X]=\sum_{i=3}^l\sum_{\sigma:i-cycle}\mathbb E[X_\sigma]=\sum_{i=3}^l \frac{n(n-1)\cdots(n-i+1)}{2i}n^{\theta i-i}\le \sum_{i=3}^l\frac{n^{\theta i}}{2i}=o(n)$$

根据马尔科夫不等式,

$$\Pr[X\ge \frac{n}{2}]\le \frac{\mathbb E[X]}{n/2}=o(1)$$

所以大概率随机图有不到$n/2$个短的环.

再保证$\Pr[\alpha(G)>m]=o(1)$

令$m=\lfloor \frac{3\ln n}{n} \rfloor$, 所以

$$\begin{aligned} \Pr[\alpha(G)\ge m] &\le \Pr[\exists S\in \binom{V}{m},\forall \{u,v\}\in \binom{S}{2},uv\not\in G]\\ &\le \binom{n}{m}(1-p)^{\binom{m}{2}}\\ &<n^me^{-p\binom{m}{2}}\\ &=(ne^{-p(m-1)/2})^m\\ &=o(1) \end{aligned}$$

根据上面两个结论,

$$\Pr[X\ge \frac{n}{2}\lor\alpha(G)\ge m]\le \Pr[X\ge \frac{n}{2}]+\Pr[\alpha(G)\ge m]=o(1)$$

因此存在图$G$, 有不到$n/2$个短环, 且$\alpha(G)<m\le 3n^{1-\theta}\ln n$.

由G构造G’

对于$G$中的每个短环去掉一个点(相邻的边也删了), 生成$G’$, 则$G’$没有短环, 因此$g(G’)\ge l$. 而且$G’$还有至多$n/2$个顶点 . 注意到这样删除边并不会让$\alpha(G)$增加, 也就是$\alpha(G’)\le\alpha(G)$. 因此

$$\chi(G')\ge \frac{n/2}{\alpha(G')}\ge\frac{n}{2m}\ge \frac{n^\theta}{6\ln n}$$

只需要让$n$足够大, 使最后的值大于$k$即可.

2 Lovász Local Lemma

考虑一系列坏事件$A_1,A_2\cdots,A_n$, 假设$\Pr[A_i]\le p$. 我们希望可能一个坏事件都不发生, 即

$$\Pr[\land_{i=1}^n \overline {A_i}]>0.$$

情形1: 完全独立事件

$$\Pr[\land_{i=1}^n \overline {A_i}]\ge (1-p)^n>0.$$

情形2: 任意相关事件

$$\Pr[\land_{i=1}^n \overline {A_i}]=1-\Pr[\lor_{i=1}^nA_i]\ge 1-np$$

因此需要$p\le 1/n$.

相关图

下面引入相关图dependency graph:
定义:令$A_1,A_2,\cdots,A_n$为一系列事件. 对于$V=\{1,2,\cdots,n\}$的图 $D=(V,E)$, 如果满足对于任意$i$, $1\le i\le n$, 事件$A_i$和事件集$\{A_j|(i,j)\not\in R\}$完全独立, 则称为$A_1,\cdots,A_n$相关图.
即$ij\in E$ <==> $A_i$和$A_j$独立
注: A和$B_1,\cdots,B_n$完全独立的定义:

$$\Pr[A|\land_{i\in S} B_i\land_{j\in R}\overline B_j]=\Pr[A]\text{ for }\forall\text{ distinct }S, R\subseteq [m]$$

例子:
独立随机变量$X_1,\cdots, X_m$. 每个事件$A_i$都是由$X_1,\cdots,X_m$中的一部分定义的. 记$v(A_i)$为决定$A_i$的最小变量集合. 则相关图$D(V,E)$定义为

$$(i,j)\in E\text{ iff }v(A_i)\cap v(A_j)\ne \emptyset$$

Lovász Local Lemma (symmetric case)

$A_1,\cdots,A_n$为一系列事件, 假设

1. $\forall~ 1\le i\le n, \Pr[A_i]\le p$,
2. $A_1,\cdots,A_n$的相关图的最大度为$d$, 且$ep(d+1)\le 1$,
   则 $$\Pr[\land_{i=1}^n \overline {A_i}]>0.$$

Lovász Local Lemma (general case)

令$D=(V,E)$为事件$A_1,\cdots,A_n$的相关图. 假设存在实数$x_1,\cdots,x_n$满足$0\le x_i<1$, 且对于任意$1\le i\le n$, 有

$$\Pr[A_i]\le x_i\prod_{(i,j)\in E}(1-x_j)$$

则

$$\Pr[\land_{i=1}^n \overline {A_i}]\ge \prod_{i=1}^n(1-x_i).$$

一般情况证明

Chain rule:

$$\Pr[\land_{i=1}^n\overline{A_i}]=\prod_{i=1}^n\Pr[\overline{A_i}|\land_{j=1}^{i-1}\overline{A_j}] =\prod_{i=1}^n(1-\Pr[A_i|\land_{j=1}^{i-1}\overline{A_j}])$$

对$m$数归证明:

$$\Pr[A_{i_1}|\overline{A_{i_2}}\cdots\overline{A_{i_m}}]\le x_i\text{ for any }\{i_i,\cdots,i_m\}$$

$m=1$时:显然.
对于一般的$m$, 假设相关图中$i_2,\cdots, i_k$和$i_1$相邻, 其他和$i_1$不相邻. 显然$k-1\le d$. 有

$$\Pr[A_{i_1}|\overline{A_{i_2}}\cdots\overline{A_{i_m}}] =\frac{\Pr[A_{i_1}\overline{A_{i_2}}\cdots\overline{A_{i_k}}|\overline{A_{i_{k+1}}}\cdots\overline{A_{i_m}}]}{\Pr[\overline{A_{i_2}}\cdots\overline{A_{i_k}}|\overline{A_{i_{k+1}}}\cdots\overline{A_{i_m}}]}$$

分子 $\le \Pr[A_{i_1}|\overline{A_{i_{k+1}}}\cdots\overline{A_{i_m}}]=\Pr[A_{i_1}]\le x_{i_1}\prod_{j=2}^k(1-x_{i_j})$
分母 $=\prod_{j=2}^k\Pr[\overline{A_{i_j}}|\overline{A_{i_{j+1}}}\cdots \overline{A_{i_m}}]=\prod_{j=2}^k(1-\Pr[A_{i_j}|\overline{A_{i_{j+1}}}\cdots\overline{A_{i_m}}])\ge \prod_{j=2}^k(1-x_{i_j})$
下面易证.

用一般情况推对称情况

令$x_1=x_2=\cdots=x_n=\frac{1}{d+1}$
则由对称情况的条件得

$$\Pr[A_i]\le \frac{1}{d+1}e^{-1}\le \frac{1}{d+1}(1-\frac{1}{d+1})^d\le \frac{1}{d+1}(1-\frac{1}{d+1})^{d_i}$$

因此可以使用一般情况证明.

2.1 Ramsey number, revisited

罗素数$R(k,l)$是最小的整数$n$满足对于$K_n$的任意二着色, 要么有红色的$K_k$, 要么有蓝色的$K_t$.
定理:
$R(k,k)\ge Ck2^{k/2}$, $C$为正常数.
证明:
要证明$R(k,k)>n$, 只要证存在$K_n$的二着色, 其中不存在同色的$K_k$.
选择一个随机的$K_n$的二着色, 每条边独立均匀随机地选择一种颜色. 对于任意$k$元集$S$, 定义$A_s$表示$S$为同色$K_k$的事件. 显然$\Pr[A_s]=2^{1-\binom{k}{2}}=p$.
对于任意$k$元集$T$, $A_s$和$A_T$相关当且仅当$|S\cap T|\ge 2$. 对于任意$S$, 满足$|S\cap T|\ge 2$的$T$的数量至多为$\binom{k}{2}\binom{n}{k-2}$. 因此$d\le \binom{k}{2}\binom{n}{k-2}$.
令$n=Ck2^{k/2}$, $C>0$为常数, 则

$$ep(d+1)\le e2^{1-\binom{k}{2}}\left(\binom{k}{2}\binom{n}{k-2}+1\right)\le 2^{3-\binom{k}{2}}\binom{k}{2}\binom{n}{k-2}\le 1$$

使用对称情况的局部引理, 没有同色$K_k$的概率为

$$\Pr[\land_{S\in \binom{[n]}{k}}\overline{A_s}]>0$$

因此存在$K_n$的无同色$K_k$的二着色, 因此

$$R(k,k)>n=Ck2^{k/2}.$$