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. If each clause of a formula in \(k\)-CNF has size exactly \(k\) and intersects no more than \(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. Assign each variable of the formula a random value (with equal probabilities, as usual) and denote by \(A_{i}\) the event that the \(i\)-th clause is not satisfied. It is clear that \(\Pr[A_{i}] = q=2^{-k}\). It is also clear that the event \(A_{i}\) cannot depend on more than \(d=2^{k-2}\) other such events: if the \(i\)-th and \(j\)-th clauses do not intersect, then \(A_{i}\) and \(A_{j}\) are independent. Since \(4qd=1\), the Local Lemma guarantees that the formula is satisfied with nonzero probability, from which we conclude that it 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.