Probability Method

Tournament的一个上界

我们再来看一个类似Ramsey Number的例子，它同样也体现了当$n$足够大时某个结构一定会出现这一性质。

Tournament Graph是一张有向图$G(V,E)$，其中任何两个点之间都有且仅有一条有向边，其中$x \to y$的有向边表示$x$赢了$y$。定义性质$P_k$成立表示随便选$k$个选手都能找到一个选手战胜了他们的所有人，形式化地：$\forall S = \dbinom{V}{k}$，$\exists x \in V \setminus S$使得$x \to y$对$\forall y \in S$成立。我们想说，对于任意固定的$k$，当$|V|$充分大时一定能找到一张Tournament Graph图使得$P_k$一定成立。我们现在要求出$|V|$的一个上界。

把图的结构作为样本空间，随机的图的结构。如果$|V|$达到足够大，即存在一张使得$P_k$成立的图，那么意味着“$P_k$成立”这一事件（对应着一系列基本事件，即图的结构）发生的概率大于0，等价于“$P_k$不成立”这一事件发生的概率小于1。$P_k$不成立的概率等价于“$\exists S\in \dbinom{V}{k}$，使得$\forall x \in V \setminus S$都$\exists y \in S$使得$x \to y$不存在”的概率。我们再次用Union Bound来放缩！我们枚举每个$S$，计算每个$S$发生这种情况的概率（再一次，对应到基本事件中这样枚举是有交集的）之和。对于每个特定的$S$，要求出任意$x$都不能战胜所有人的概率，我们利用概率的性质：发现“$x_1$不能战胜所有人”这一事件和“$x_2$不能战胜所有人”这一事件是独立的（用容斥原理验证），更一般的，对于多个人的情形他们是“相互独立”的。某个人不能战胜所有人的概率是$1-\dfrac{2^{n-k}}{2^n}=1-2^{-k}$，因此我们就直接依据独立性得到整个概率为$(1-2^{-k})^{n-k}$。这样对于所有$S$累加得$\dbinom{n}{k}(1-2^{-k})^{n-k}$。只要令它小于1我们就得到了一个上界。可以验证当$n=O(k^22^k)$时满足。

Cut的一个下界

刚才的概率方法都是基于“要证明某种结构存在，转化为证明存在的概率大于0”这一思想的。概率方法的应用不止这一种。下面我们会看到，如果要证明某种规模的结构存在，比如要证明某个随机变量是可能大于$t$的，可以证明该随机变量的期望大于$t$，这样也能直接说明随机变量大于$t$是可能的。

我们要证明：对于任意给定的$G=(V,E)$，一定存在一个割$S \subseteq E$使得$|S| \geq \dfrac{|E|}{2}$。

我们来计算$E[|S|]$。我们的样本空间是所有可能的cut，这等价于所有可能的划分点集的选取。 这也等价于我们让每个点有1/2的概率落到点集$X$，1/2的概率落到点集$Y$。那么一条边$(u,v)$是割边当且仅当“$u \in X,v \in Y$”或“$u \in Y,v \in X$”。根据期望的线性性，我们只需累加每条边成为割边的期望，即累加$E[|S|]=\sum\limits_{(u,v) \in E}E[(u,v)\text{ is cut}]=\sum\limits_{(u,v) \in E} (\Pr[u\in X]\Pr[v \in Y]+\Pr[u\in Y]\Pr[v \in X])$ $\sum\limits_{(u,v)\in E}\dfrac{1}{2}\cdot \dfrac{1}{2}+\dfrac{1}{2}\cdot \dfrac{1}{2}=\dfrac{|E|}{2}$。证毕。

既然证明了这样的割存在，那么是否存在一种算法来具体地找出这样一个割呢？

一个割是由划分点集确定的，因此如果令变量$X_v=\mathbb1[v \in T]$表示点$v$是否落到点集$T$中，那么割的大小$|S|$就可以由某个函数$f(X_1,\cdots,X_n)$给出。因此现在我们要计算$E[f(X_1,\cdots,X_n)]$，那么根据全期望公式得到$E[f(X_1,\cdots,X_n)]=$ $E[f(X_1,\cdots,X_n)|X_1=0]\Pr[X_1=0]+E[f(X_1,\cdots,X_n)|X_1=1]\Pr[X_1=1]$。而由于我们已经知道$E[|S|] \geq \dfrac{|E|}{2}$，因此$E[f(X_1,\cdots,X_n)|X_1=0]$与$E[f(X_1,\cdots,X_n)|X_1=1]$中至少有一个$\geq \dfrac{|E|}{2}$。而关键在于，这两个“子期望”本身是能被计算的，只需要用刚才一模一样的方法即可。这样我们就能得到$X_1$究竟该取怎么样的值才能让期望的割边数量大于$|E|/2$。依此类推，不断使用全期望公式我们就能依次给出每个变量$X_i$的取值，从而最终得到了一个能给出能使得大于等于$|E|/2$的划分，也就给出了一个符合要求的割。

Dominating Set的一个上界

一个图的支配集（Dominating Set）是一个点的子集，使得这些点覆盖了所有节点。这里覆盖指有边相连，即一个点要么被选进了支配集要么有一个相邻节点被选进了支配集。

对此我们有一个直观——如果图上点的最小度数越大，那么支配集的规模就能越小。我们Claim：如果无向图$G=(V,E)$的点的最小度数为$\delta$，那么存在一个大小为$\dfrac{n(1+\ln(\delta+1))}{\delta+1}$的支配集。

我们依旧用概率法来证明。随机产生给定图的一个支配集：假设每个点有大小为$p$的概率被选进支配集$S$。每次生成的$S$不一定形成了一个支配集，可能存在若干点没有“被支配”，把这些点收集进集合$T$。那么显然$S \cup T$就是一个支配集了。最小支配集一定小于等于它的大小。我们通过求解$|S \cup T|$的期望来给出证明。根据期望的线性性，$E[|S|]=\sum\limits_{x \in V}\mathbb1[x \in S] = np$。$E[|T|]=\sum\limits_{x \in V}\mathbb1[x \in T]=\sum\limits_{x \in V}\Pr[x\in T]$，而$\Pr[x \in T]$是容易计算的，$x\in T$当且仅当$x \notin S$且所有与$x$相邻的点$\not\in S$，这个概率为$(1-p)^{1+\deg(x)}$。而$\deg(x) \geq \delta$恒成立，因此$(1-p)^{1+\deg(x)} \leq (1-p)^{1+\delta}$恒成立（越乘越小）。所以我们证明了$\Pr[x \in T] \leq (1-p)^{1+\delta}$恒成立。于是有$E[|T|] \leq n(1-p)^{1+\delta}$。再次根据期望的线性性，$E[|S \cup T|]=E[|S|]+E[|T|]$ $\leq np+n(1-p)^{1+\delta}$。右侧是一个关于$p$的函数$f(p)$，当$p$取不同值的时候它给出支配集的不同上界。那我们肯定希望能取一个尽量小的上界，因此我们希望求出$f(p)$的最小值。为了计算方便，我们做放缩$1+x \leq e^x$，得到$f(p) \leq np+n(e^{-p})^{1+\delta}=n(p+e^{-p(1+\delta)})=g(p)$。在$p=\dfrac{\ln(\delta +1)}{\delta+1}$时取到最小值$\dfrac{n(1+\ln(\delta+1))}{\delta+1}$。因此$E[|S \cup T|] \leq \dfrac{n(1+\ln(\delta+1))}{\delta+1}$，所以原图一定存在大小为$\dfrac{n(1+\ln(\delta+1))}{\delta+1}$的支配集。

Max Independent Set大小的一个下界

用类似的想法，一个图里边越多我们就会期待独立集越小。我们Claim：$\forall d\geq 1$，如果无向图$G=(V,E)$中包含有$\dfrac{nd}{2}$条边，就一定存在一个大小为$\dfrac{nd}{2}$的独立集。

随机独立集，以概率$p$入选集合$S$。它不一定是独立集，假设这些点之间形成了边集（导出子图的边）$T$，那么对于每条边删掉一个点就一定得到了一个独立集。删掉的点数就是$|T|$。和上面类似，我们计算期望，有$E[|S|]=np$。而$E[|T|]=\sum\limits_{(u,v) \in E}\mathbb{1}[u \in S \land v \in S] = p \times p \times |E| = \dfrac{1}{2}p^2nd$。因此$E[|S|-|T|]=np-\dfrac{1}{2}p^2nd \geq \dfrac{n}{d}-\dfrac{n}{2d}=\dfrac{n}{2d}$。

图的Girth与染色数

无向图的Girth定义为最小环所含的边数（无环图的Girth为$\infty$），记为$Girth(G)$。比如，二分图由于没有奇环所以Girth至少为4。

图的染色数即最少需要几种染色才能使得存在一种染色使得每条边的两个端点的颜色都不同，记为$\chi(G)$。比如，完全图的染色数等于点数，树的染色数为2，二分图的染色数也为2。

直观上我们倾向于认为，图越稠密，则Girth应当越小，染色数应当越大。也就是我们认为Girth和染色数应当一大一小。但事实上我们发现我们的直观错误了，我们能证明Girth和染色数都很大——

Erdős定理指出，$\forall \ell,k \in \N$，存在一个图$G$满足$Girth(G)\geq \ell$和$\chi(G) \geq k$。

要用概率法证明这个定理，我们需要随机生成一张图。我们采取的方法是，给定顶点总个数$n$，接下来对于任意的点对以概率$p$在它们之间生成一条边。显然，$p$越大生成的图越稠密，$p$越小越稀疏。根据我们的直观，$p$越大时Girth应当越小，那么满足$Girth(G)\geq\ell$越困难。而如果减小$p$，则$p$越小满足$\chi(G)\geq k$越困难。如果我们找到一个临界点$p_{girth},p_{\chi}$，使得$p<p_{girth}$时$\Pr[Girth(G)\geq\ell] > \dfrac{1}{2}$，$p>p_{\chi}$时$\Pr[\chi(G) \geq k]>\dfrac{1}{2}$，并且$p_{\chi}<p_{girth}$，那么我们就能保证$(p_\chi,p_{girth})$内的某个$p$能生成一张同时满足这两个条件的图，因为$\Pr[Girth(G)\geq\ell] > \dfrac{1}{2}$保证了超过一半的图满足第一个条件，所以只有不到一半的图不满足第一个条件。而$\Pr[\chi(G) \geq k]>\dfrac{1}{2}$又告诉我们超过一半的图满足第二个条件，因此在那不到一半的不满足第一个条件的图即便全都不满足第二个条件，在剩下的满足第一个条件的图里也必须有满足第二个条件的图，这样就保证了同时满足两个条件的图存在了。

先来求$p_{girth}$，我们希望它尽量大。为了表示$Girth(G) \geq \ell$这一事件，定义随机变量$X$表示图中$< \ell$的环的数量，这样$X=0$这一事件就可以等价地代替$Girth(G) \geq \ell$这一事件了。我们要求$\Pr[X=0]>\dfrac{1}{2}$时$p$的取值范围，可以让$\Pr[X=0]>\dfrac{1}{2}$取反，等价于$\Pr[X\geq 1] < \dfrac{1}{2}$。由Markov不等式得$\Pr[X \geq 1] \leq \dfrac{E[X]}{1}=E[X]$。因此我们只需选取合适的$p$满足$E[X]<\dfrac{1}{2}$就能保证原条件成立。我们可以利用期望的线性性来计算$E[X]$：枚举环的大小，然后依次枚举固定大小的环的互异点列，得到$E[X]=\sum\limits_{i=3}^{\ell-1}\sum\limits_{v_1..v_i}\Pr[(v_1,\cdots,v_i)\text{ is a circle}]$，而$i$个点形成环的概率可以这样计算：枚举点的全排列，每个全排列给出了环的一种顺序，要恰好使得这个环成立需要恰好有这样顺序的$i$条边，因此概率为$p^i$。全排列共有$i!$个，但要注意我们重复枚举了环，因为环上任意一个点作为起点是等价的，同时以顺时针或逆时针的方式枚举环也是等价的，因此每个环都恰好被枚举了$2i$次。综上写出$E[X]=\sum\limits_{i=3}^{\ell-1}\dbinom{n}{i}\cdot p^i\cdot \dfrac{i!}{2i}=\sum\limits_{i=3}^{\ell-1}\dfrac{n!}{i!(n-i)!}\cdot p^i\cdot \dfrac{i!}{2i}$ $=\sum\limits_{i=3}^{\ell-1}p^i\cdot \dfrac{n!}{2i(n-i)!}$ $=\sum\limits_{i=3}^{\ell-1}\dfrac{(n)(p)(n-1)(p)\cdots(n-i+1)(p)}{2i}$ $\leq \sum\limits_{i=3}^{\ell-1}\dfrac{n^ip^i}{2i}$ $\leq \sum\limits_{i=3}^{\ell-1}(np)^i$ $\leq (np)^3 \dfrac{(np)^{\ell-3}-1}{np-1} \leq (np)^{\ell}$。为使$(np)^{\ell} < \dfrac{1}{2}$，只需取$p=O(\dfrac{1}{n})$数量级。这样我们求出了$p_{girth}$的一个范围。

接着来算$p_\chi$。同样考虑反面，$\Pr[\chi(G) \geq k]>\dfrac{1}{2}$等价于$\Pr[\chi(G) < k]<\dfrac{1}{2}$。我们发现，如果一个图的染色数为$k$，那么一定可以划分成$k$个独立集，根据鸽巢原理一定存在某个独立集的大小是$\geq\dfrac{n}{k}$的。因此我们可以由$\chi(G)<k$推出最大独立集$\alpha(G) \geq \dfrac{n}{k}$，或者更一般地，这说明$\alpha(G)\geq\dfrac{n}{k}$这一事件“包含的图更多”，因此$\Pr[\chi(G)<k] \leq \Pr[\alpha(G)\geq\dfrac{n}{k}]$。下面我们对于随机图来估计$\Pr[\alpha(G) \geq x]$（也可以用上面的类似的期望方法，这里我们尝试别的做法来丰富思维）：“最大独立集$\geq x$”这一事件等价于“存在一个大小为$x$的独立集”这一事件（充分必要），因此$\Pr[\alpha(G)\geq x]=\Pr[存在大小为x的独立集]$，对此我们可以用熟悉的Union Bound来放缩，枚举大小为$x$的点集，对于每个点集要求成为独立集，再对所有可能的点集累加，由于方案之间可能有重复，所以我们可能放大了这个概率，因此写出$\leq \dbinom{n}{x}(1-p)^{\binom{x}{2}}$，$1-p$用指数放缩成$e^{-p}$，$\dbinom{n}{x}=\dfrac{n!}{x!(n-x)!}$ $\leq \dfrac{n!}{(n-x)!}\leq n^x$，综上$\Pr[\alpha(G) \geq x]\leq n^xe^{-p\cdot \frac{x(x-1)}{2}}=\left(ne^{-\frac{p(x-1)}{2}}\right)^x$。为了使它$<\dfrac{1}{2}$，取$p>\dfrac{3\ln n}{x}$。因此$p_\chi$的数量级应为$\Omega(\dfrac{\ln n}{n})$。

所以我们不幸地发现，我们放缩的结果是$p_\chi$要大过$p_{girth}$。所以我们必须调整我们的结果。调整的方法是，在求$p_{girth}$时我们曾要求$X=0$，即小于$\ell$的环的个数为0。现在我们放松一点限制，可以容许$X$非0，在这样的基础上我们直接在图上删除若干个节点就能再次保证$X=0$，我们来看看这样的估计是否会更优一点。为了使$p_{girth}$大过$p_\chi$，我们取$p=\dfrac{\ln^2 n}{n}$，那么根据$E[X]\leq(np)^\ell$得到$E[X]\leq (\ln n)^{2\ell}$。根据Markov不等式，$\Pr[X \geq \dfrac{n}{2}] \leq \dfrac{E[X]}{\frac{n}{2}} \leq \dfrac{2(\ln n)^{2\ell}}{n}$，当$n$足够大时就有$\Pr[X \geq \dfrac{n}{2}]<\dfrac{1}{2}$，所以$\Pr[X < \dfrac{n}{2}]>\dfrac{1}{2}$。至此我们把$X=0$放松为了$X < \dfrac{n}{2}$，由于两个概率都大于$1/2$并且$p$的范围有交集了，我们保证了一定存在一个图染色数$\geq k$并且只有不超过$n/2$个大小$<\ell$的环。

同时，我们在求$p_\chi$时已经证明了当$p > p_\chi$时$\Pr[\alpha(G) \geq \dfrac{n}{k}]<\dfrac{1}{2}$，因此$\Pr[\alpha(G)<\dfrac{n}{k}]>\dfrac{1}{2}$。也就是说，把第一个条件换成“最大独立集$<\dfrac{n}{k}$”也是成立的。

那么对于每个小环，我们删去一个顶点，这样就保证了没有$< \ell$的环了。而新图上的独立集一定也是原图上的独立集（因为新图上没有的边原图上也一定没有），所以新图的最大独立集$\alpha'(G')$一定变小了，因此依然$<\dfrac{n}{k}$。而我们知道根据鸽巢原理任何时候染色数乘以最大独立集都不能小于顶点数，因此$\chi'(G')\alpha'(G') \geq \dfrac{n}{2}$。所以推出$\chi'(G') \geq \dfrac{k}{2}$。这样我们就得到了一张新图，它的染色数$\geq k/2$，最小环$\geq \ell$。由于$k,\ell$是任意的，所以就像数分中取$\varepsilon$一样，我们实际上已经证明了要证的结论了。