Lovász 局部引理

并集界要求所有坏事件概率之和小于一，忽略了许多事件彼此无关。局部引理只为每个事件支付其依赖邻居造成的代价：只要事件足够少见且依赖图足够稀疏，全部坏事件同时避开的概率仍为正。它证明的是一个全局交事件存在，却只检查局部条件。

一组可代入的 SAT 参数 ​

设 CNF 的每个子句恰含 $k$ 个互异变量，每个变量至多出现在 $L$ 个子句中。独立均匀赋值，令 $A_i$ 为第 $i$ 个子句全部不满足，则 $p=2^{-k}$。共享变量的子句连边，每个子句至多与 $d=k(L-1)$ 个其他子句相邻；全部非邻居只依赖本子句之外的随机变量，因此满足联合独立性要求。充分条件成为

例如 $k=8,L=10$ 时，$d\le 72$，左边至多 $73e/256\approx 0.775<1$，所以无论子句总数多大，公式都存在满足赋值。并集界却只在子句数小于 $256$ 时直接给出正概率。这里证明存在性；Moser–Tardos 重采样算法公理库Moser–Tardos 重采样算法Moser–Tardos resampling · 算法化局部引理在独立变量模型中局部重采样坏事件，用见证树证明终止与每个事件的期望修复次数。在这个独立变量模型中构造满足赋值，并给出 $m$ 个子句下至多 $m/72$ 的期望重采样次数及相应索引实现成本。

常数与依赖图的边界 ​

多加依赖边会削弱充分条件，漏掉真实依赖则可能使结论失效。只验证两两独立或协方差为零不够。常见变体 $4pd\le 1$ 须附带 $d\ge 1$；若 $d=0$，直接用联合独立性和 $p<1$ 得 $\text{Pr}(\bigcap _i\overline{A_i})=\prod _i(1-\text{Pr}(A_i))>0$。不能把 $d=0,p=1$ 代进 $4pd\le 1$ 而声称可避免必然事件。这些界都是充分条件，超出它们不等于无解。

概率方法公理库概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。借独立性公理库独立性Statistical independence从概率表理解独立性，区分两两、相互和条件独立，并用可计算反例澄清零协方差与条件均值的限度。结构超越简单并集界，依赖图公理库有限简单无向图Graph · Finite simple undirected graph · 图由有限顶点集与无序二元顶点子集组成的边集所确定的简单无向图。编码局部相互作用。超图公理库超图Hypergraph边可以连接任意多个顶点而非仅两个顶点的离散结构。染色、无重复词和 SAT 可满足性是典型应用；在变量模型中，Moser–Tardos 重抽样还把存在性证明变成构造算法。若坏事件全局强相关，则应改用浓缩、二阶矩或其他工具。