Lovász 局部引理

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

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

若每个坏事件概率至多 $p$，且至多依赖另外 $d$ 个坏事件，对称形式的充分条件是

例如变量模型中，每个子句只与共享变量的子句相依；远处子句无需计入 $d$。把统计相关性误作依赖图定义会出错：所需条件是事件与所有非邻居事件族相互独立（或满足相应 lopsidependency），不只是两两协方差为零。

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