Introduction to the Lovász Local Lemma (LLL)
Audience – Graduate students in combinatorics or theoretical computer science
Prerequisites – Familiarity with elementary probability, the union bound, and basic graph theory.
Goal – To present the LLL from first principles, prove both the symmetric and asymmetric versions, discuss edge cases, and sketch the algorithmic Moser–Tardos framework.
1. Motivation
The probabilistic method often shows that a combinatorial object with desirable properties exists by exhibiting a probability space in which the bad events have small probability. The classic tool is the union bound:
[ \Pr!\left[\bigcup_{i=1}^n A_i\right] \le \sum_{i=1}^n \Pr[A_i]. ]
If each (\Pr[A_i] \le p) and (p < 1/n), then the union bound guarantees a positive probability that none of the (A_i) occurs.
However, in many problems the bad events are not independent; they may be correlated in a structured way. In such cases the union bound can be grossly pessimistic. The Lovász Local Lemma gives a powerful alternative that exploits limited dependency.
2. The Dependency Graph
Let (\mathcal{A} = {A_1,\dots,A_n}) be a finite set of events in a probability space. We say that two events (A_i) and (A_j) are dependent if they are not independent.
Definition (Dependency graph).
A simple undirected graph (G=(V,E)) on vertex set ([n]) is a dependency graph for (\mathcal{A}) if for every (i \in [n]),
[ A_i \text{ is independent of } {A_j : j \notin {i} \cup \Gamma_G(i)}, ]
where (\Gamma_G(i)) denotes the neighborhood of (i) in (G). Intuitively, each event may depend only on its neighbors in (G).
Example.
In the graph coloring problem, when we colour vertices randomly, the event that a particular edge is monochromatic depends only on the two endpoints, so the dependency graph is the line graph of the original graph.
3. First-Principles Derivation
3.1 The Symmetric LLL
Theorem (Symmetric Local Lemma).
Let (\mathcal{A}) be a set of events with a dependency graph (G) of maximum degree (d). Suppose that each event satisfies
[ \Pr[A_i] \le p \quad\text{for all }i, ] and that
[ ep(d+1) \le 1. \tag{LLL} ]
Then
[ \Pr!\left[\bigcap_{i=1}^n \overline{A_i}\right] > 0. ]
Proof Sketch (inductive + induction on the number of events)
We prove by induction on (n) the stronger statement:
[ \Pr!\left[\bigcap_{i=1}^n \overline{A_i}\right] ;\ge; \prod_{i=1}^n (1-p_i), ] where (p_i = \Pr[A_i]). The induction step uses the following key inequality (the inductive step):
[ \Pr!\left[\overline{A_i} \mid \bigcap_{j \in S} \overline{A_j}\right] ;\ge; 1 - p_i \prod_{j \in \Gamma_G(i)} \frac{1}{1 - p_j}, ] for any set (S) that contains all neighbors of (i).
The derivation relies on the following lemma:
Lemma (Conditional Probability Bound).
Let (B) be an event that is independent of all events in (\mathcal{A}) except possibly (A_1,\dots,A_k). Then [ \Pr[B \mid \bigcap_{i=1}^k \overline{A_i}] ;\ge; \Pr[B] \prod_{i=1}^k \frac{1}{1 - \Pr[A_i]}. ]
Proof of the lemma.
We use induction on (k). For (k=0), it’s trivial. Assume true for (k-1). Write
[ \Pr[B \mid \bigcap_{i=1}^k \overline{A_i}] = \frac{\Pr[B \cap \overline{A_k} \cap \bigcap_{i=1}^{k-1} \overline{A_i}]}{\Pr[\overline{A_k}\mid \bigcap_{i=1}^{k-1}\overline{A_i}] \Pr[\bigcap_{i=1}^{k-1}\overline{A_i}]}. ]
Using independence of (B) from (A_k) we get
[ \Pr[B \mid \bigcap_{i=1}^k \overline{A_i}] = \frac{\Pr[B\mid \bigcap_{i=1}^{k-1}\overline{A_i}] \Pr[\overline{A_k}\mid \bigcap_{i=1}^{k-1}\overline{A_i}]}{\Pr[\overline{A_k}\mid \bigcap_{i=1}^{k-1}\overline{A_i}] \Pr[\bigcap_{i=1}^{k-1}\overline{A_i}]} = \Pr[B\mid \bigcap_{i=1}^{k-1}\overline{A_i}]. ]
Thus the induction step works, and the lemma follows by multiplying the bounds for each (A_i). ∎
Applying this lemma to (B = \overline{A_i}) and using (\Pr[\overline{A_i}]=1-p_i) yields
[ \Pr[\overline{A_i}\mid \bigcap_{j\in S}\overline{A_j}] ;\ge; (1-p_i)\prod_{j