Lovász Local Lemma

The Lovász Local Lemma (LLL) is a powerful tool for proving that the probability of avoiding all "bad" events is positive, even when the events are not independent. It requires only that each bad event has low probability and limited dependence on other events.

Symmetric and Asymmetric Forms

Definition7.4Dependency Graph

A dependency graph for events $A_1, \ldots, A_n$ is a graph $G$ on $[n]$ such that each $A_i$ is mutually independent of $\{A_j : \{i, j\} \notin E(G)\}$ . Each event depends on at most $d = \Delta(G)$ other events.

Definition7.5Lovász Local Lemma (Symmetric Form)

Let $A_1, \ldots, A_n$ be events with a dependency graph of maximum degree $d$ . If $\Pr[A_i] \leq p$ for all $i$ and $ep(d + 1) \leq 1$ , then $\Pr\left[\bigcap_{i=1}^n \overline{A_i}\right] > 0.$

ExampleHypergraph Coloring

A $k$ -uniform hypergraph where each edge intersects at most $d$ other edges is 2-colorable if $d \leq 2^{k-1}/e - 1$ . Proof: Color each vertex red/blue uniformly at random. For each edge $e$ , let $A_e$ be the event that $e$ is monochromatic. Then $\Pr[A_e] = 2 \cdot 2^{-k} = 2^{1-k}$ , and $A_e$ depends on at most $d$ other events. By the symmetric LLL, $e \cdot 2^{1-k} \cdot (d + 1) \leq 1$ suffices.

Asymmetric Version

Definition7.6Lovász Local Lemma (General Form)

Let $A_1, \ldots, A_n$ be events with dependency graph $G$ . If there exist $x_1, \ldots, x_n \in (0, 1)$ such that for all $i$ : $\Pr[A_i] \leq x_i \prod_{j: \{i,j\} \in E(G)} (1 - x_j),$ then $\Pr[\bigcap_{i=1}^n \overline{A_i}] \geq \prod_{i=1}^n (1 - x_i) > 0$ .

RemarkAlgorithmic LLL

Moser and Tardos (2010) gave a constructive proof of the LLL: the Moser-Tardos algorithm repeatedly finds a violated event and resamples its variables. Under the LLL conditions, this terminates in expected polynomial time, providing an efficient algorithm to find the desired combinatorial structure.

Example$k$-SAT Application

A $k$ -CNF formula where each variable appears in at most $2^k / (ek)$ clauses is satisfiable. This follows from the LLL applied to the random assignment: each clause fails with probability $2^{-k}$ , and each clause shares variables with at most $k \cdot 2^k/(ek) - 1$ other clauses.