形式陈述

设有限事件族 $A_1,\dots,A_n$$A_1,\dots ,A_n$ 有依赖图：每个 $A_i$$A_i$ 与所有非邻居事件生成的 $\sigma$$\sigma$-代数独立。非对称 Lovász 局部引理称，若存在 $x_i\in[0,1)$$x_i\in [0,1)$ 使

$$ \Pr(A_i)\le x_i\prod_{j\in\Gamma(i)}(1-x_j) $$$$\text{Pr}(A_i)\le x_i\prod _{j\in \mathrm{\Gamma }(i)}(1-x_j)$$

对每个 $i$$i$ 成立，则

$$ \Pr\left(\bigcap_i\overline{A_i}\right)>0. $$$$\text{Pr}\left(\bigcap _i\overline{A_i}\right)>0.$$

对称形式中，若 $\Pr(A_i)\le p$$\text{Pr}(A_i)\le p$，每个事件至多依赖 $d$$d$ 个其他事件，且

$$ ep(d+1)\le1, $$$$ep(d+1)\le 1,$$

则所有坏事件同时避免的概率为正。Moser–Tardos 重采样在独立变量模型下给出相应算法化版本。

直觉

并界把所有坏事件概率直接相加；局部引理利用每个事件只与少量邻居相互作用，即使事件总数很大，也能证明全局同时避开。

例子与边界

图着色中可把“某条边两端同色”作为坏事件；两条边若不共享随机变量即可独立，依赖度由局部邻接控制。事件之间不要求全局互相独立，若真独立则结论更容易。依赖图中的边可以多于实际依赖，得到更弱但仍正确的条件；漏掉真实依赖则论证失效。对称条件有多种常数形式，如 $4pd\le1$$4pd\le 1$ 等充分条件，不能把充分条件误写成必要条件。局部引理给正概率但原始证明不直接给高效样本；算法化版本还要求事件由独立变量局部决定并可重采样。

推论与应用

局部引理构造稀疏依赖下的着色、无模式序列、超图性质和满足性赋值。

参考资料

• Noga Alon and Joel H. Spencer, The Probabilistic Method, 4th ed., Wiley, 2016，Ch. 5, Lovász Local Lemma and algorithmic forms。
• Béla Bollobás, Modern Graph Theory, Springer, 1998，Ch. VII, local lemma in random structures。