洛瓦兹筛
洛瓦兹局部引理
给定一个“坏事件”的集合\(\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处理问题经常会放过头。
洛瓦兹局部引理就是这样一个利用了事件本事之间联系的定理。我们定义一个关于坏事件集合的“依赖图”\(G([m],E)\)，满足：如果\(B_i\)与\(B_j\)不独立，则\(i,j\)之间必须连一条边。这里我们没有要求如果\(i,j\)有边必须能推出\(B_i,B_j\)不独立，因此依赖图是不唯一的。一个完全图一定是一个合法的依赖图。设\(d\)是依赖图的最大度数，直观上\(d\)越小说明事件之间的相关性越低。洛瓦兹局部引理指出，如果\(\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\)是自然对数。
我们之后将会对更一般的情况给出证明，这里我们先来通过例子来进一步洛瓦兹局部引理在说什么。
如果所有事件都互斥（互斥即没有交集。我们知道两个互斥事件不可能同时发生，所以同时发生的概率为0，而两个事件的概率相乘不等于0，因此互斥事件一定不独立），此时的依赖图只能是完全图。因此\(d=m-1\)。因此如果\(p<\dfrac{1}{em}\)，那么满足洛瓦兹定理的条件，坏事件有可能都不发生。
如果所有事件都相互独立，那么\(d\)可以取0。此时如果\(p<\dfrac{1}{e}\)就可以推出坏事件可能都不发生。
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。
现在我们可以用洛瓦兹局部引理了！两个\(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}}\)就能保证不存在同色子图，这样我们就找到了一个新的更大的下界。