Lovász local lemma

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$.

Going deeper

For a student

The local lemma is one of the main tools of the probabilistic method. Unlike Boole's inequality, 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.