Lesson 7

Let us give an example of using Lovász's local lemma, showing how easily nontrivial things can be derived from it. We say that two clauses of a formula in CNF intersect if they have at least one common variable (this variable may appear in these two clauses with different signs).

Theorem. For \(k\ge 1\), if every clause of a CNF formula consists of exactly \(k\) literals on distinct variables and intersects at most \(2^{k-2}\) other clauses, then the formula is satisfiable.

For example, if each clause of the formula contains exactly ten variables and intersects no more than \(256\) other clauses, then the formula is satisfiable. At the same time, we do not impose any restrictions on the number of clauses or the number of variables! We also note that it is not difficult to construct an unsatisfiable formula in \(k\)-CNF with exactly \(2^{k}\) clauses.

Proof. For \(k=1\), the intersection bound is \(1/2\), so different clauses use disjoint variables and the formula is satisfiable. For \(k\ge 2\), assign each variable independently and uniformly at random. Let \(A_{i}\) be the event that clause \(i\) is not satisfied. Then \(\Pr[A_{i}]=q=2^{-k}\). Let \(\Gamma(A_{i})\) consist of the events corresponding to other clauses that share a variable with clause \(i\). By assumption, \(|\Gamma(A_{i})|\le d=2^{k-2}\). Every event outside \(\Gamma(A_{i})\cup\{A_{i}\}\) is determined only by variables outside clause \(i\). Thus \(A_{i}\) is independent of that entire collection, even if those events depend on one another. Since \(4qd=1\), the Local Lemma guarantees that the formula is satisfied with positive probability, and hence is satisfiable.◼

The obtained result is nonconstructive (as is Lovász's Local Lemma itself): it does not tell us how to quickly find a satisfying assignment. It can be made constructive, but it is not so easy.