Skip to main content
Logo image

Applied Combinatorics

Section 16.7 The Lovász Local Lemma

Even though humans seem to have great difficulty in providing explicit constructions for exponentially large graphs which do not have complete subgraphs or independent sets of size \(n\text{,}\) such graphs exist with great abundance. Just take one at random and you are almost certain to get one. And as a general rule, probabilistic techniques often provide a method for finding something that readily exists, but is hard to find.
Similarly, in the probabilistic proof that there exist graphs with large girth and large chromatic number (Theorem 11.7), we actually showed that almost all graphs have modest sized independence number and relatively few small cycles, provided that the edge probability is chosen appropriately. The small cycles can be destroyed without significantly changing the size of the graph.
By way of contrast, probabilistic techniques can, in certain circumstances, be used to find something which is exceedingly rare. We next present an elegant but elementary result, known as the Lovász Local Lemma, which has proved to be very, very powerful. The treatment is simplified by the following natural notation. When \(E\) is an event in a probability space, we let \(\overline{E}\) denote the complement of \(E\). Also, when \(\cgF=\{E_1,E_2,\dots,E_k\}\) we let
\begin{equation*} \prod_{E\in\cgF}E=\prod_{i=1}^k E_i=E_1E_2E_3\dots E_k \end{equation*}
denote the event \(E_1\cap E_2\cap\dots\cap E_k\text{,}\) i.e., concatenation is short hand for intersection. These notations can be mixed, so \(E_1\overline{E_2}\overline{E_3}\) represents \(E_1\cap \overline{E_2}\cap\overline{E_3}\text{.}\) Now let \(\cgF\) be a finite family of events, let \(E\in\cgF\) and let \(\cgN\) be a subfamily of \(\cgF-\{E\}\text{.}\) In the statement of the lemma below, we will say that \(E\) is independent of any event not in \(\cgN\) when
\begin{equation*} P(E|\prod_{F\in\cgG}\overline{F})=P(E) \end{equation*}
provided \(\cgG\cap\cgN=\emptyset\text{.}\)
We first state and prove the lemma in asymmetric form. Later, we will give a simpler version which is called the symmetric version.
We proceed by induction on \(\cgG\text{.}\) If \(|\cgG|=1\) and \(\cgG=\{E\}\text{,}\) we are simply asserting that \(P(\overline{E})\ge 1-x(E)\text{,}\) which is true since \(P(E)\le x(E)\text{.}\) Now suppose that \(|\cgG|=k\ge2\) and that the lemma holds whenever \(1\le |\cgG|\lt k\text{.}\) Let \(\cgG =\{E_1,E_2,\dots,E_k\}\text{.}\) Then
\begin{equation*} P(\prod_{i\ge1}^k \overline{E_i})=P(\overline{E_1}|\prod_{i=2}^k\overline{E_i}) P(\overline{E_2}|\prod_{i=3}^k\overline{E_i})P(E_3|\prod_{i=4}^k\overline{E_i})\dots \end{equation*}
Now each term in the product on the right has the following form:
\begin{equation*} P(\overline{E}|\prod_{F\in\cgF_E}\overline{F}) \end{equation*}
where \(|\cgF_E|\lt k\text{.}\)
So, we done if we can show that
\begin{equation*} P(\overline{E}|\prod_{F\in\cgF_E}\overline{F})\ge 1- x(E) \end{equation*}
This is equivalent to showing that
\begin{equation*} P(E|\prod_{F\in\cgF_E}\overline{F})\le x(E) \end{equation*}
Suppose first that \(\cgF_E\cap\cgN(E)=\emptyset\text{.}\) Then
\begin{equation*} P(E|\prod_{F\in\cgF_E}\overline{F})=P(E)\le x(E). \end{equation*}
So we may assume that \(\cgF_E\cap\cgN(E)\neq\emptyset\text{.}\) Let \(\cgF_E=\{F_1,F_2,F_r,F_{r+1},F_{r+2},\dots, F_t\}\text{,}\) with \(F_i\in\cgN_E\) if and only if \(r+1\le i\le t\text{.}\) Then
\begin{equation*} PE|\prod_{F\in\cgF_E}\overline{F})= \frac{P(E\prod_{F\in\cgF_E\cap\cgN(E)}\overline{F}|\prod_{F\in\cgF_E-\cgN(E)}\overline{F})} {P(\prod_{F\in\cgF_E\cap \cgN(E)}\overline{F})} \end{equation*}
Consider first the numerator in this last expression. Note that
\begin{equation*} P(E\prod_{F\in\cgF_E\cap\cgN(E)}\overline{F}|\prod_{F\in\cgF_E-\cgN(E)}\overline{F})\le P(E|\prod_{F\in\cgF_E\cap\cgN(E)}\overline{F})\le x(E)\prod_{F\in\cgF_E\cap\cgN(E)}(1-x(F)) \end{equation*}
Next, consider the denominator. By the inductive hypothesis, we have
\begin{equation*} P(\prod_F\in\cgF_E\cap\cgN(E)\overline{F}\ge \prod_{F\in\cgF_E\cap\cgN(E)}(1-x(F)). \end{equation*}
Combining these last two inequalities, we have
\begin{equation*} P(E|\prod_{F\in\cgF_E}\overline{F})\le x(E)\prod_{\cgN(E)-\cgF_E}(1-x(F))\le x(E), \end{equation*}
and the proof is complete.
Now here is the symmetric version.
Set \(x(E)=1/(d+1)\) for every event \(E\in\cgF\text{.}\) Then
\begin{equation*} P(E)\le p\le \frac{1}{e(d+1)}\le x(E)\prod(F\in\cgN(E)(1-\frac{1}{d+1}). \end{equation*}
A number of applications of the symmetric form of the Lovász Local Lemma are stated in terms of the condition that \(4pd\lt 1\text{.}\) The proof of this alternate form is just a trivial modification of the argument we have presented here.