---
tag: 35YQ94FNV1
kind: statement
role: lemma
name: Lovász local lemma
msc: [05D40, 60C05]
uses: [0NFPJVJJHX, 031TPJVS74, 001B78R0DJ, 00C0BR7D7H]
about: [3B55HNS754]
sources:
  - url: https://en.wikipedia.org/wiki/Lov%C3%A1sz_local_lemma
same_as:
  wikidata: Q831721
  wikipedia: Lovász local lemma
---

## Statement

Let $A_1, \dots, A_n$ be [[events|031TPJVS74]] in a [[probability space|0NFPJVJJHX]].
Let $D$ be a [[graph|00C0BR7D7H]] on the vertex set $\set{1, \dots, n}$.
Suppose each $A_i$ is [[mutually independent|001B78R0DJ]] of the family of events $A_j$ with $j \ne i$ and $j$ not adjacent to $i$.

1. (General form.) Suppose there are real numbers $x_1, \dots, x_n \in [0, 1)$ with $\Pr(A_i) \le x_i \prod_{j \sim i} (1 - x_j)$ for each $i$, where $j \sim i$ means that $j$ is adjacent to $i$. Then $\Pr\big(\bigcap_i \overline{A_i}\big) \ge \prod_i (1 - x_i) > 0$.
2. (Symmetric form.) Suppose each vertex of $D$ has degree at most $d$, and $\Pr(A_i) \le p$ for each $i$, with $e \, p \, (d + 1) \le 1$. Then $\Pr\big(\bigcap_i \overline{A_i}\big) > 0$.

## Remarks

The proof shows by induction on $\abs{S}$ that $\Pr\big(A_i \mid \bigcap_{j \in S} \overline{A_j}\big) \le x_i$ for each set $S$ not containing $i$ for which the conditioning event has positive probability.
The symmetric form follows from the general form with $x_i = 1/(d + 1)$, using $(1 - 1/(d+1))^d \ge 1/e$.
For example, let $\varphi$ be a formula in conjunctive normal form in which each clause has exactly $k$ literals on distinct variables.
If each clause shares variables with at most $d$ other clauses and $e (d + 1) \le 2^k$, then $\varphi$ is satisfiable.
Indeed, under a uniformly random assignment each clause fails with probability $2^{-k}$.
Some limit on dependence is needed: if $A_1$ is an event of probability $1/2$ and $A_2$ is its complement, then no outcome avoids both.
Here $d = 1$ and $p = 1/2$, and $e p (d + 1) = e > 1$.

## Explanations

### L1 human

Suppose you want to avoid many bad events at once, and each bad event is unlikely.
If the events were independent, you could avoid all of them with positive probability.
The local lemma says that this still works when each event depends on only a few others.
This is often enough to prove that a good object exists.

### L2 human

The local lemma is one of the main tools of the [[probabilistic method|3B55HNS754]].
Unlike [[Boole's inequality|0EGSEE9J9R]], it can give positive probability even when the sum of the probabilities of the bad events is large.
Typical applications are colourings of hypergraphs, satisfiability of sparse formulas, and lower bounds for Ramsey numbers.
Moser and Tardos gave an efficient algorithm that finds an outcome avoiding all events, under the same hypotheses in the variable setting.