the Lovasz Local Lemma
/ LOH-vahs /
The Lovasz Local Lemma is the tool that rescues the probabilistic method when the union bound fails. The basic method shows a good object exists by proving P(some bad event occurs) < 1, usually via the union bound P(union of B_i) <= sum P(B_i). But when there are many bad events, this sum exceeds 1 even though each individual event is rare. If the bad events were fully independent, P(none occurs) = product of (1 - P(B_i)) > 0 whenever each P(B_i) < 1, so existence would follow trivially. Reality sits between these extremes: bad events are usually neither disjoint nor independent, but each event depends on only a few others. The Local Lemma exploits exactly this sparse dependence.
Set up a dependency graph: vertices are the bad events B_1, ..., B_n, and B_i is joined to B_j if B_i is mutually independent of the collection of all events not adjacent to it. The symmetric Local Lemma states that if each P(B_i) <= p, each event depends on at most d others, and the criterion e * p * (d + 1) <= 1 holds (e = 2.718..., Euler's number), then P(no bad event occurs) > 0 — so a configuration avoiding all bad events exists. The general (asymmetric) form replaces the single bound by a system: if one can assign numbers x_i in (0,1) with P(B_i) <= x_i times the product over neighbours j of (1 - x_j), then again P(none occurs) > 0, and in fact P(none) >= product of (1 - x_i) > 0. The proof is an induction showing the conditional probability of each B_i, given that any subset of the others is avoided, stays below x_i.
Its importance is that it turns 'rare and weakly dependent' into 'simultaneously avoidable', which the union bound cannot do. Classic applications: proper colourings of hypergraphs (each colour-constraint touches few others), satisfiability of k-SAT formulas where each clause shares variables with few other clauses, and many results where the dependency degree d grows but stays controlled. The honest caveat is that the criterion ep(d+1) <= 1 is essential and tight in spirit: it is not magic. If the bad events are too probable or too densely dependent the lemma gives nothing, and the constant e cannot in general be improved (Shearer determined the exact threshold). Moreover the classical lemma is non-constructive — it proves existence but historically gave no efficient way to find the good configuration, a gap closed only later by Moser-Tardos.
k-SAT: a CNF formula where every clause has exactly k literals and each variable appears in few clauses is satisfiable. Pick each variable's truth value by a fair coin. The bad event B_i = 'clause i is unsatisfied' has P(B_i) = 2^(-k). If each clause shares a variable with at most d other clauses and e * 2^(-k) * (d+1) <= 1, i.e. d <= 2^k/e - 1, the LLL guarantees a satisfying assignment exists. The union bound, by contrast, fails as soon as there are more than 2^k clauses.
Symmetric LLL: ep(d+1) <= 1 makes rare, sparsely-dependent bad events simultaneously avoidable.
The LLL is not magic: the criterion ep(d+1) <= 1 (or the asymmetric x_i system) is essential, the constant e cannot generally be improved (Shearer's bound is tight), and the classical lemma is non-constructive.