Lovasz Local Lemma
The probabilistic method is a non-constructive way of proving the existence of an object having certain property. The argument usually goes as follows: a randomly selected object has the desired property with probability strictly positive, thus there must exist an object having the property; however, we do not know how to explicitly construct such an object. The Lovasz Local Lemma is an example of the probabilistic method.
The Lovasz Local Lemma
Suppose that we have a collection of events \(\{A_1,\ldots, A_n\}\), and consider the probability that none of them happens:
\[
{\bf Pr}[\wedge_{i=1}^{n} \overline{ A_i}].
\]
If the events are mutually independent, and if there exists \(p < 1\) such that \({\bf Pr}[ A_i] \leq p\) for every \(i\), then \[ {\bf Pr}[\wedge_{i=1}^{n} \overline{A_i}] = \prod_{i=1}^{n} {\bf Pr}[\overline{A_i}] \geq (1-p)^n > 0.
\]
Note that, although \((1-p)^n\) is exponentially small in \(n\), it is still positive.
The Lovasz Local Lemma generalizes “mutually independent” condition to allow limited dependencies among the events.
We say an event \(A\) is mutually independent of a set of events \(\{ B_i\}_{i=1}^n\) if for any subset \(I\subseteq [n]\), it holds that \({\bf Pr}[A\mid \wedge_{i\in I}B_i] = {\bf Pr}[A]\).
[The Lovasz Local Lemma] Let \(A_1, A_2,\ldots, A_n\) be a set of (bad) events such that each event \(A_i\) is mutually independent of all but at most \(d\) of the other events. Denote by \(D_i\subseteq [n]\) the index of the events that \(A_i\) depends on. Suppose there are real numbers \(x_1,x_2,\ldots, x_n\) such that for all \(i\), we have \(0\leq x_i < 1[/latex] and
\[
{\bf Pr}[A_i] \leq x_i\prod_{j\in D_i}(1-x_j).
\]
Then
\[
{\bf Pr}\left[\bigwedge_{i=1}^{n} \overline{A_i}\right] > \prod_{i=1}^n(1-x_i) >0.
\]
The Proof
First we prove by induction that, for any [latex]S\subset [n]\) and any \(i\notin S\),
\[
{\bf Pr}\left[A_i\mid \bigwedge_{j\in S} \overline{A_j}\right] \leq x_i.
\]
This is obviously true if \(|S| = 0\). Now suppose it holds for any subsets of \([n]\) of size less than \(s\). Consider a subset \(S\) of size exactly \(s\). We divide \(S\) into two parts: \(S_1 = S\cap D_i\) and \(S_2 = S\setminus S_1\). Then, by the fact that
\[
{\bf Pr} [A \mid B\wedge C] = \frac{{\bf Pr} [A \wedge B\mid C] }{{\bf Pr} [B \mid C] },
\]
we have
\[
{\bf Pr} \left[A_i\mid \bigwedge_{j\in S} \overline{A_j}\right] = \frac{ {\bf Pr} [A_i\wedge\bigwedge_{k\in S_1}\overline{A_k}\mid \bigwedge_{j\in S_2} \overline{A_j}] }{ {\bf Pr} [\bigwedge_{k\in S_1}\overline{A_k}\mid \bigwedge_{j\in S_2} \overline{A_j}] }.
\]
The numerator is bounded above by the mutually independence,
\[
{\bf Pr} [A_i\wedge\bigwedge_{k\in S_1}\overline{A_k}\mid \bigwedge_{j\in S_2} \overline{A_j}]
\leq {\bf Pr} [A_i \mid \bigwedge_{j\in S_2} \overline{A_j}]
={\bf Pr} [A_i] \leq x_i\prod_{j\in D_i}(1-x_j).
\]
The denominator is bounded below by the induction hypothesis. If \(|S_1| = 0\), the denominator is 1. Otherwise, let \( S_1 =\{k_1,\ldots, k_r\}\), then by the chain rule,
\[
{\bf Pr} \left[\bigwedge_{k\in S_1}\overline{A_k}\mid \bigwedge_{j\in S_2} \overline{A_j}\right]
= \prod_{l=1}^{r} {\bf Pr} \left[ \overline{A_{k_l}} \mid \bigwedge_{l’< l}\overline{A_{l'}}\wedge \bigwedge_{j\in S_2} \overline{A_j}\right]
\geq \prod_{l=1}^{r} (1 - x_{k_l}) =\prod_{k\in S_1} (1 - x_{k})
\]
Substituting the bounds for the numerator and denominator, we have
\[
{\bf Pr}\left[A_i\mid \bigwedge_{j\in S} \overline{A_j}\right] \leq x_i.
\]
Applying the chain rule, we get
\[
{\bf Pr}\left[\bigwedge_{i=1}^{n} \overline{A_i}\right]
= \prod_{i=1}^{n} {\bf Pr}\left[\overline{A_i} \mid \bigwedge_{j< i} \overline{A_j}\right]
\geq \prod_{i=1}^{n} (1-x_i) >0.
\]
The Symmetric Case
Here we give a specific case of the lemma. In the lemma statement, suppose we have \({\bf Pr}[A_i]\leq p\) and \(ep(d+1) \leq 1\); then it also holds that
\[
{\bf Pr}\left[\bigwedge_{i=1}^{n} \overline{A_i}\right] > 0.
\]
The result holds by letting \(x_i = \frac{1}{d+1}\), and by the fact that for any \(d \geq 1\),
\[
\left(1 – \frac{1}{d+1}\right)^d > \frac{1}{e}.
\]
Satisfiability of k-SAT
Applying the Lovasz Local Lemma, we can derive the following. For any \(k\)-CNF where no variable appear in more than \(2^{k-2} / k\) clauses, it is satisfiable.
Suppose we have a \(k\)-CNF formula with \(n\) variables and \(m\) clauses. We randomly assign each variable with 0 or 1 with equal probability. For each clause, we define an event that it is not satisfied. That is, for \(i=1,\ldots, m\), let \(A_i\) be the event that the i-th clause is not satisfied. Then we have \({\bf Pr}[A_i] = 2^{-k}\equiv p\).
Note that each event \(A_i\) is independent of another event \(A_j\) as long as the two clauses do not share a common variable. Since each variable appears in at most \(2^{k-2} / k\) clauses, we have each \(A_i\) is independent of all but at most \(d\) other events, where
\[
d \leq k \cdot 2^{k-2} / k = 2^{k-2}
\]
Thus for \(k > 3\), we have \(\)ep(d+1) < 1[/latex], which fits the condition in the symmetric version. This implies, with positive probability, none of the clauses is not satisfied (all clauses are satisfied). Thus, the CNF is satisfiable. Note that, the condition in the symmetric case can be replace by [latex]4pd \leq 1[/latex]. This implies for [latex]k\leq 3[/latex], the above result also holds.