Lovász Local Lemma

洛瓦兹局部引理(Lovász Local Lemma, LLL)

给定一个“坏事件”的集合$\mathcal{B}=\{B_1,\cdots,B_m\}$，其中$\Pr[B_i]<1$。当我们希望一个坏事件都不发生的时候，我们等价于希望有坏事件发生的概率$<1$，即$\Pr[\bigcup\limits_{i=1}^{m}B_i]<1$。根据以往的做法，我们可以根据Union Bound直接放缩为$\sum\limits_{i=1}^{m}\Pr[B_i]$，证明它小于1即可。

Union Bound是对任何事件集都成立的，也就是说Union Bound的放缩一定没能利用到“坏事件”本身之间的联系。这将会导致用Union Bound处理问题经常会放过头。

LLL就是这样一个利用了事件本事之间联系的定理。我们定义一个关于坏事件集合的“依赖图”$G([m],E)$，满足：如果$B_i$与$B_j$不独立，则$i,j$之间必须连一条边。这里我们没有要求如果$i,j$有边必须能推出$B_i,B_j$不独立，因此依赖图是不唯一的。一个完全图一定是一个合法的依赖图。设$d$是依赖图的最大度数，直观上$d$越小说明事件之间的相关性越低。LLL指出，如果$\exists 0\leq p<1$使得$\Pr[B_i] \leq p$恒成立（即坏事件的概率存在上界$p$），且存在某个度数为$d$的依赖图，使得$p,d$满足$p(d+1)<\dfrac{1}{e}$，那么可以推出坏事件都不发生的概率大于0，即$\Pr[\bigcap\limits_{i=1}^{m}\overline{B_i}]>0$。其中$e$是自然对数。

我们之后将会对更一般的情况给出证明，这里我们先来通过例子来进一步LLL在说什么。

如果所有事件都互斥（互斥即没有交集。我们知道两个互斥事件不可能同时发生，所以同时发生的概率为0，而两个事件的概率相乘不等于0，因此互斥事件一定不独立），此时的依赖图只能是完全图。因此$d=m-1$。因此如果$p<\dfrac{1}{em}$，那么满足洛瓦兹定理的条件，坏事件有可能都不发生。

如果所有事件都相互独立，那么$d$可以取0。此时如果$p<\dfrac{1}{e}$就可以推出坏事件可能都不发生。

我们看到，LLL告诉我们只要确定出每个事件与其相关的事件个数（局部性）的一个上界，我们就有一种方法来分析是否能使所有事件都不发生。当我们用Union Bound放缩时，我们利用的是每个事件的概率加和；使用洛瓦兹引理时，我们利用的是事件之间的相关性。

Ramsey数的更好下界

我们给出过$R(s,s)>2^{s/2}$。其实它是由$\Pr[\bigcup\limits_{S\in\binom{[n]}{k}}B_S]\leq \dbinom{n}{k} 2^{1-\binom{k}{2}}<1$推得的，可以解出更精确的下界$n\leq \left(\dfrac{1}{e\sqrt{2}}+o(1)\right)k\cdot 2^{\frac{k}{2}}$。我们做的工作就是为了使$\Pr[\bigcap\limits_{i=1}^{m}\overline{B_i}]>0$，当时我们使用的是Union Bound。

现在我们可以用LLL了！两个$k$子图$S,T$如果只有不超过1个公共点，那么它们没有公共边， 所以是独立的。所以只有可能那些有超过1个公共点的子图间不独立，所以某个$k$子图最多可能拥有$\dbinom{k}{2}\dbinom{n-2}{k-2}$个与它不独立的子图，对应的依赖图上度数不可能超过它。所以$d \leq \dbinom{k}{2}\dbinom{n-2}{k-2}$。我们的坏事件是子图的边同色，所以$\Pr[B_i]$恒为$2 \times \dfrac{1}{2^\binom{k}{2}}$。所以取$p=2^{1-\binom{k}{2}}$，代入$p(d+1)<\dfrac{1}{e}$解得只要$n \leq \left(\dfrac{\sqrt{2}}{e}+o(1)\right)k\cdot 2^{\frac{k}{2}}$就能保证不存在同色子图，这样我们就找到了一个新的更大的下界。

k-SAT

对于一个$m$个clause的CNF，每个clause的literals都为$k$，它由$n$个变量构成：$\phi=C_1 \land C_2 \land \cdots \land C_m$。定义$d(x_i)$表示有多少个clause里出现了变量$x_i$，$d(x_i)$的最大值称为这个CNF的度数$\Delta$。我们现在想通过LLL求出当$\Delta$满足什么条件时，一定能找到一组变量的赋值使得CNF满足。

定义坏事件$B_i$表示clause[i]不满足，由于clause内部是“或”，不满足当且仅当自变量的赋值使得每个参与运算的都为0，因此$\Pr[B_i] = 2^{-k}$。$B_i,B_j$如果没有公共变量就一定独立，而由于$\Delta$的限制一个clause最多只能与$k(\Delta-1)$个clause不独立，因此在依赖图上$d\leq k(\Delta-1)$。直接代入LLL可得：只要$2^{-k}\cdot k\Delta<\dfrac{1}{e}$就能使得所有坏事件都不发生的概率大于0，等价于，只要$\Delta<\dfrac{2^k}{ek}$时一定能找到一组变量的值使得CNF为true。

独立集

假设图$G(V,E)$上点的最大度数为$\Delta$，将$V$划分成$m$个集合$V_1,\cdots,V_m$，且$|V_i| \geq k$。当$k$满足什么条件时，存在一种方案从每个$V_i$中挑出一个点$u_i$使得$\{u_i\}$构成一个独立集？

不妨设每个$|V_i|$都为$k$，因为如果某些$|V_i|>k$，我们可以删点后分析，删点后的图中的独立集一定也是原图中的独立集，因为遗失的边都是关于那些删掉的点的。接下来我们用概率法，随机从每个集合中挑一个点，因此每个点被挑中的概率就恰好是$\dfrac{1}{k}$。我们对每条端点不属于同一个$V_i$的边定义坏事件，根据条件坏事件应当是这条边的两个点都被挑中了，这发生的概率为$\dfrac{1}{k^2}$。按照惯例，接下来我们要分析依赖图来使用LLL，两个坏事件（两条边）如果没有公共点，并且四个点分属不同的$V_i$，那么这两个事件独立；如果存在两个点在同一个集合，那么这两个事件是互斥的，不可能独立；如果存在公共点，也即存在一个公共点， 那么可能不独立。后面两种情况可以统一为“不能存在两条边中有两个端点处于同一个集合”的情况，因此对于每一个坏事件（一条边）与其不独立的$\leq 2[(k-1)\Delta+\Delta-1]=2k\Delta-2<2k\Delta -1$个（稍微放松了）。于是代入LLL可得$\dfrac{1}{k^2}\cdot 2k\Delta<\dfrac{1}{e}$，解得$k>2e\Delta$。

非对称洛瓦兹局部引理

在我们成功应用洛瓦兹局部引理的案例中，我们定义的坏事件都具有对称性，甚至坏事件发生的概率都相等，因此给出的概率上界就是概率本身。而如果坏事件的概率本身具有某种较大的波动性，那么用上界放缩就不那么有效了。对于这样的问题我们也用相应的改进办法，就称为“非对称的洛瓦兹局部引理”：

如果每个$B_i$都对应着一个$x(B_i)$，它在$(0,1)$实数范围内取值，记$\text{Nei}(B_i)$表示依赖图上$B_i$的邻居节点，那么如果概率满足$\Pr[B_i]\leq x(B_i)\prod\limits_{\text{Nei}(B_i)}(1-x(B_i))$，就可以推出$\Pr[\bigcap\limits_{i=1}^m \overline B_i]\geq \prod\limits_{i=1}^m (1-x(B_i))>0$。

函数$x(B_i)$在这里没有明确的组合意义。实际上在其它研究中人们已经找出了一些它的意义，但这些意义比较复杂，这里就不讨论了。

我们大致能够看出这是一个比原来的定理更一般的定理。实际上，令$x(B_i)$恒等于$\dfrac{1}{d+1}$，那么条件可以写为$\Pr[B_i]\geq x(B_i)\prod\limits_{\text{Nei}(B_i)}(1-x(B_i))$ $\geq \dfrac{1}{d+1}\cdot \left(1-\dfrac{1}{d+1} \right)^d>\dfrac{e^{-1}}{(d+1)}$。所以只要$p(d+1)>\dfrac{1}{e}$就能推出结论。

下面我们来证明。

根据链式法则，我们可以把$\Pr[\bigcap\limits_{i=1}^m \overline B_i]$写作$\prod\limits_{i=1}^m \Pr[\overline B_i\mid \bigcap\limits_{j<i} \overline B_j]$。记$F_S:= \bigcap\limits_{i\in S,S \in [n]}\overline B_i$，即坏事件集合$S$通通不发生这一事件，那么又可以把它写作$\prod\limits_{i=1}^m\left(1-\Pr[B_i\mid F_{[i-1]}]\right)$。那么要证$\Pr[\bigcap\limits_{i=1}^m \overline B_i]\geq \prod\limits_{i=1}^m (1-x(B_i))$，只需证$\Pr[B_i\mid F_{[i-1]}] \leq x(B_i )$。为此，我们可以转而证明$\Pr[B_i \mid F_S] \leq x(B_i)$对所有$i \notin S$成立。

对$S$的大小归纳。当$S=\emptyset$时，$F_S=1$，那么根据$\Pr[B_i]\leq x(B_i)\prod\limits_{\text{Nei}(B_i)}(1-x(B_i))$直接得到$\Pr[B_i\mid F_S]=\Pr[B_i] \leq x(B_i)$。

当$S\neq \empty$时，如果$S$中的所有坏事件$B_j$都和$B_i$独立，此时也有$\Pr[B_i\mid F_S]=\Pr[B_i] \leq x(B_i)$。否则，我们把$S$划分成两部分$S_1,S_2$，其中$S_1$是所有与$B_i$不独立的坏事件构成的（在依赖图上必须与$i$有边），$S_2$是所有独立的构成的。那么$\Pr[B_i \mid F_S]$现在写作$\Pr[B_i \mid F_{S_1} \cap F_{S_2}]$ $=\dfrac{\Pr[B_i \cap F_{S_1}\cap F_{S_2}]}{\Pr[F_{S_1}\cap F_{S_2}]}$。它等价于$\dfrac{\Pr[B_i \cap F_{S_1} \cap F_{S_2}]}{\Pr[F_{S_2}]}\cdot \dfrac{\Pr[F_{S_2}]}{\Pr[F_{S_1} \cap F_{S_2}]}=\Pr[B_i \cap F_{S_1}\mid F_{S_2}] \cdot \dfrac{1}{\Pr[F_{S_1}\mid F_{S_2}]}$。我们分别放缩分子和分母，为了证明它小于$x(B_i)$，分子应当放大，分母应当放小。分子$\Pr[B_i \cap F_{S_1} \mid F_{S_2}] \leq \Pr[B_i \mid F_{S_2}]$，而根据我们的分类$B_i$与$F_{S_2}$是独立的，于是$\Pr[B_i | F_{S_2}] =\Pr[B_i] \leq x(B_i)\prod\limits_{\text{Nei}(B_i)}(1-x(B_i))$。而对于分母，$\Pr[F_{S_1}\mid F_{S_2}]$，不妨设$S_1=\{1,2,\cdots,r\}$，那么它写作$\Pr[\bigcap\limits_{i=1}^r \overline B_i \mid F_{S_2}]$。它可以根据链式法则写作$\prod\limits_{i=1}^{r}\Pr[\overline{B_i}\mid F_{S_2} \cap \bigcap\limits_{i=k}^{i-1} \overline B_k]$。其中$F_{S_2} \cap \bigcap\limits_{i=k}^{i-1} \overline B_k$对应着某个更小的$S'$的$F_{S'}$，所以把每个$\Pr[\overline{B_i}\mid F_{S_2} \cap \bigcap\limits_{i=k}^{i-1} \overline B_k]$写作$\Pr[\overline{B_i}\mid F_{S'}]=1-\Pr[B_i \mid F_{S'}]$，用归纳假设$\Pr[B_i\mid F_{S'}]\leq x(B_i)$得$\Pr[\overline{B_i}\mid F_{S_2} \cap \bigcap\limits_{i=k}^{i-1} \overline B_k] \geq 1-x(B_i)$。因此综上$\Pr[F_{S_1}\mid F_{S_2}]\geq\prod\limits_{i=1}^{r}(1-x(B_i))$。在依赖图上考虑，不仅这些不独立事件会连边，独立事件也可能连边，乘上更多小于1的数以后它变得更小，因此写出$\geq \prod\limits_{j \in \text{Nei}(B_i)}(1-x(B_j))$。综上$\dfrac{\Pr[B_i \cap F_{S_1}\mid F_{S_2}] }{\Pr[F_{S_1}\mid F_{S_2}]} \leq \dfrac{x(B_i)\prod\limits_{\text{Nei}(B_i)}(1-x(B_i))}{\prod\limits_{j \in \text{Nei}(B_i)}(1-x(B_j))}-x(B_i)$。证毕。

非对称Ramsey数

我们到目前为止都只给出了$R(s,s)$的下界。现在通过非对称的LLL，我们能给出$R(r,s)$的下界。先来研究$R(k,3)$。

要使得$K_n$的任何边染色方案都不能存在$K_3$的全红子图和$K_k$的全蓝子图，我们定义坏事件$A_S$为大小为$3$的子图$S$​全红，坏事件$B_T$为大小为$k$的子图$T$全蓝，整个坏事件集合就由这两种坏事件构成。对于某个$A_S$，在依赖图中与它相邻的$A_{S'}$不超过$\dbinom{3}{2} \times (n-3)=3(n-3)$个（即统计与$S$公共点超过两个的$S'$），与它相邻的$B_T$不超过$\dbinom{3}{2}\dbinom{n-3}{k-2}$，尽管如此，我们可以把它放松成$\dbinom{n}{k}$；与$B_T$相邻的$B_{T'}$不超过$\dbinom{k}{2}\dbinom{n-k}{k-2}$，我们也把它放松成$\dbinom{n}{k}$，与$B_T$相邻的$A_S$不超过$\binom{k}{2}(n-2)=\dfrac{k(k-1)(n-2)}{2}$，把它放松成$\dfrac{nk^2}{2}$。现在随机给图上的边染色，以$p$的概率染红色，$1-p$的概率染蓝色。于是$\Pr[A_S]=p^3,\Pr[B_T]=(1-p)^{\binom{k}{2}}$。现在我们设两个实数$0<\alpha,\beta<1$使得$p^3 \leq \alpha(1-\alpha)^{3(n-3)}(1-\beta)^{\binom{n}{k}}$；$(1-p)^{\binom{k}{2}} \leq \beta(1-\alpha)^{\frac{nk^2}{2}}(1-\beta)^{\binom{n}{k}}$，那么如果把$\alpha,\beta$分别视为我们的神秘函数$x(A_S),x(B_T)$，我们就符合非对称LLL的条件了——因为我们先前把指数放大了，把指数缩小为依赖图上的真正度数以后，如果$\alpha,\beta$可以作为函数的取值，我们就真的满足了非对称LLL的条件。现在的问题是，当$n$取什么样的值时可以解出这样的$\alpha,\beta$？我们的全部要求就是，解出$0<p,\alpha,\beta<1$这三个量使得以上两个不等式满足，这样就能直接得到一个能满足LLL要求的条件。我们发现，当$n=O\left(\dfrac{k^2}{\log k}\right)$这是可以做到的，于是我们得到了$R(k,3)$的一个下界$C\dfrac{k^2}{\log k}$。

用类似的方法，我们还可以求得$R(k,4)>k^{\frac{5}{2}+o(1)}$，这已经是目前全世界已知的$R(k,4)$的最好下界了。

算法化洛瓦兹局部引理

我们之前讨论的洛瓦兹局部引理都只给出了“存在性”，那么我们能不能给出一个高效地找到这个解的算法呢？以寻找k-SAT为例，我们希望能找到一个使得CNF为true的赋值。一个最简单的想法是不停的随机生成变量的赋值，直到CNF满足为止。如果CNF被满足的概率是$\dfrac{1}{\text{poly}(n)}$级别的，那么这个方法确实可以期望在多项式时间内找到解。遗憾的是，这个概率是指数级别的，所以我们必须寻找更高效的算法。

2009 年R. Moser给出了一个非常简单的找到k-SAT问题的解的算法，并成功证明了这个算法在期望线性的时间内就可以找到一组可满足解——在生成了一组随机的赋值以后，如果不满足，相比于直接对全部变量进行重新赋值，该算法考虑只对没被满足的子句上的变量进行重新赋值。具体过程如下：

如果当前的赋值不能满足题目条件，那么找到第一个不满足的clause，记为$C_i$，调用"fix(i)"：对于$C_i$中所涉及到的所有变量重新随机赋值，接着对于分布在各个其它的$C_j$里的这些变量，找到第一个不满足的$C_j$（包括它自己）调用"fix(j)"。

Moser证明了当$d<2^{k-3}-1$时（这时符合LLL的条件的）期望只调用$O(m)$次fix就能找到一组解。

先来看这个算法的正确性。这个算法的fix函数的执行过程可以看作是一棵树，树的一个节点就是对某个clause的fix。对于某个节点，假设它代表fix(x)，那么它还将有一个子树， 因为当我们给如果一个clause重新赋值以后，我们还将找到许多不满足的其它“相邻”clause来调用fix。显然在整个子树执行完毕之后clause(x)一定已经满足了，并且在回到父节点之后clause(x)不会再次不满足，否则说明在其它过程中x的值再次被修改了，而我们知道递归地，只要修改我们就一定会把其内部的所有变量改对为止。

下面来分析复杂度。当我们谈Moser算法的期望的时候，我们的样本空间是什么呢？样本空间应当是我们每一次选择的随机赋值的所有可能形，如果把它想象成一段C++程序，样本空间就是我们的“随机种子”的取值范围。假设一个Moser算法执行了至少$T$次fix，那么我们就生成了$T$次clause的赋值，对应着$kT$个01随机数，以及最初的$n$个赋值。所以我们的样本空间大小为$2^{n+kT}$。只要我们能求出“会使得算法执行至少$T$次fix的概率”是多少，我们就可以根据定义求出期望了。但这是不容易直接求出的。我们来考虑用一个二进制串来表示我们的“DFS树”的形态：对于每个节点把它的子节点用二进制从0开始编码，而所需要的二进制的位数只需要$O(\log d)$。我们再单独用一个0代表向下往儿子方向走，1表示像父节点走，我们就可以用一个二进制串模拟出一个DFS树，而这个二进制串只需要$n+m+(\log (d+1)+2)(T-1)$位。这说明符合要求的超过$T$次fix的算法过程不超过$2^{n+m+(\log(d+1)+2)(T-1)}$个，所以概率$\Pr[fix \geq T] \leq \dfrac{2^{n+m+(\log(d+1)+2)(T-1)}}{2^{n+kT}} \leq 2^{m-T}$。即运行了$T$次fix以后算法仍不能停止的概率$\leq 2^{m-T}$，等价于运行了$m+T$次以后不停止的概率$\leq 2^{-T}$，这样我们就保证了概率小于1。我们计算算法执行每一次fix的期望——总的执行次数等于执行每一次的概率之和。而执行第$m+i$次fix的概率一定不超过$2^{-i}$。因此期望$E[T]\leq m+\sum\limits_{i=1}^{+\infty}2^{-i}=O(m)$。