The Lovász Local Lemma: When Rare Bad Events Can All Be Avoided

Precise statement: the symmetric and general forms

Let A₁, …, Aₙ be events in a probability space. The dependency graph is a graph on {1,…,n} whose edge set records dependence: each Aᵢ is required to be mutually independent of the family {Aⱼ : j not adjacent to i} — mutual, meaning independent of every Boolean combination of those Aⱼ, not merely pairwise. Write Γ(i) for the neighbors of i.

General LLL (Erdős–Lovász, 1975). If there exist reals x₁,…,xₙ ∈ (0,1) with

P(Aᵢ) ≤ xᵢ · ∏_{j ∈ Γ(i)} (1 − xⱼ) for all i,

then P(⋂ᵢ overline{Aᵢ}) ≥ ∏ᵢ (1 − xᵢ) > 0.

Symmetric corollary. If each P(Aᵢ) ≤ p and each Aᵢ depends on at most d others (|Γ(i)| ≤ d), and

e · p · (d + 1) ≤ 1,

then P(⋂ᵢ overline{Aᵢ}) > 0. Here e = 2.718… is Euler's number; taking xᵢ = 1/(d+1) uniformly and using (1 − 1/(d+1))ᵈ ≥ 1/e recovers the symmetric bound from the general one.

The picture: locality beats the union bound

The union bound says: to avoid all bad events, demand ∑ P(Aᵢ) < 1. That is hopelessly wasteful when n is large — a million events each of probability 10⁻³ already blow past 1, even though intuitively they might never collide.

The Local Lemma replaces the global budget with a local one. Imagine each bad event as a lit fuse that can only ignite its immediate neighbors in the dependency graph. If every fuse is unlikely to light AND touches only a few others, the fire cannot spread system-wide, no matter how many fuses there are. Crucially the bound e·p·(d+1) ≤ 1 has no n in it: you can have arbitrarily many events. What matters is the local density of dependence, not the total count. The xᵢ in the general form are 'reserved-probability' dials — each Aᵢ pre-pays a fraction xᵢ, and its neighbors' non-occurrence gives it enough breathing room ∏(1−xⱼ) to still be avoidable.

Key idea of the proof: conditional probabilities by induction

The heart is a bound on conditioned probabilities. Let S ⊆ {1,…,n}, and write A_S for the event ⋂_{j∈S} overline{Aⱼ}. The claim proved by induction on |S| is:

P(Aᵢ | A_S) ≤ xᵢ for every i ∉ S.

Mechanism. Split S into S₁ = S ∩ Γ(i) (neighbors) and S₂ = S \ S₁. By the definition of conditional probability, P(Aᵢ | A_S) = P(Aᵢ ∩ A_{S₁} | A_{S₂}) / P(A_{S₁} | A_{S₂}). For the numerator, Aᵢ is independent of the non-neighbors S₂, so it is ≤ P(Aᵢ | A_{S₂}) = P(Aᵢ) ≤ xᵢ ∏_{j∈Γ(i)}(1−xⱼ). For the denominator, expand A_{S₁} as an intersection and apply the inductive hypothesis to each neighbor in turn (each conditioning set is strictly smaller), giving a lower bound ≥ ∏_{j∈Γ(i)}(1−xⱼ). The ∏(1−xⱼ) factors cancel, leaving ≤ xᵢ. Finally P(⋂ overline{Aᵢ}) = ∏ᵢ P(overline{Aᵢ} | ⋂_{j 0.

Canonical example: k-SAT with bounded clause overlap

Take a Boolean formula in conjunctive normal form where every clause has exactly k literals. Assign each variable True/False independently with probability ½. A clause is violated only when all k of its literals are false, so P(clause Aᵢ violated) = 2⁻ᵏ =: p.

Two clauses are dependent only if they share a variable. Suppose each clause shares a variable with at most d other clauses. The symmetric LLL guarantees a satisfying assignment exists as soon as

e · 2⁻ᵏ · (d + 1) ≤ 1, i.e. d ≤ 2ᵏ/e − 1.

So any k-CNF in which every clause overlaps at most about 2ᵏ/e others is satisfiable — a purely local structural condition, independent of the number of clauses or variables. For k=3 this permits each clause to share variables with up to ⌊8/e − 1⌋ = 1 other clause; the constant improves under sharper analyses (Gebauer–Szabó–Tardos: satisfiable up to ~2ᵏ⁺¹/(e·k) neighbors), and the threshold is essentially tight.

Why the hypotheses matter, and what breaks

Mutual (not pairwise) independence is essential. The dependency-graph condition demands Aᵢ be independent of every Boolean combination of its non-neighbors. Pairwise independence is too weak: three events can be pairwise independent yet jointly forced (e.g., parity constraints), and the induction collapses.

The slack e·p·(d+1) ≤ 1 cannot be pushed to 1 with a smaller constant. Shearer (1985) determined the exact threshold for the symmetric case; Shearer's bound is (d−1)^{d−1}/dᵈ ≈ 1/(e·d), showing the factor e is asymptotically sharp — you cannot replace e·p·(d+1) ≤ 1 by anything materially weaker for general dependency graphs. Drop the sparsity entirely (d unbounded) and the conclusion fails: with n independent fair coins, avoiding all n 'heads' events has probability 2⁻ⁿ → 0, and here each event's neighborhood is empty so LLL does apply — but glue the events with enough dependence and positivity genuinely vanishes. LLL sits precisely between the trivial union bound (∑p<1) and the impossible (arbitrary dependence).

Applications and the constructive breakthrough

The LLL is a cornerstone of the probabilistic method. It yields: proper colorings of graphs and hypergraphs with far fewer colors than greedy bounds; the existence of r-colorings of hypergraphs where no edge is monochromatic (property B); low-discrepancy set systems; Latin-transversal and Ramsey-type constructions; and packet-routing schedules with near-optimal congestion (Leighton–Maggs–Rao).

For 35 years LLL was non-constructive — it proved a good object exists but gave no algorithm to find it. In 2010 Moser and Tardos supplied a stunningly simple fix: in the 'variable model' (each Aᵢ determined by a subset of independent random variables), just resample the variables of any currently-violated event, repeat until none is violated. Under e·p·(d+1) ≤ 1 this halts in expected ≤ ∑ᵢ xᵢ/(1−xᵢ) resamples. Moser's entropy-compression analysis — a witness log of resamples cannot be shorter than the randomness it encodes — is now a technique in its own right. LLL thus became fully algorithmic, powering derandomization and distributed graph coloring.

Union bound vs. Lovász Local Lemma vs. Moser–Tardos: what each requires and delivers

Tool	Key hypothesis	Conclusion	Constructive?
Union bound	∑ᵢ P(Aᵢ) < 1	P(⋂ overline{Aᵢ}) ≥ 1 − ∑P(Aᵢ) > 0	No (just positivity)
Symmetric LLL	P(Aᵢ) ≤ p, degree ≤ d, e·p·(d+1) ≤ 1	P(⋂ overline{Aᵢ}) > 0	Not directly
General LLL	P(Aᵢ) ≤ xᵢ·∏_{j∈Γ(i)}(1−xⱼ), some xᵢ∈(0,1)	P(⋂ overline{Aᵢ}) ≥ ∏(1−xᵢ) > 0	Not directly
Moser–Tardos	Variable model + e·p·(d+1) ≤ 1	Finds an assignment avoiding all Aᵢ	Yes — expected ≤ ∑ xᵢ/(1−xᵢ) resamples