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\), 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 (), 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\)\(\overline{E}\)complement of event \(E\). Also, when \(\cgF=\{E_1,E_2,\dots,E_k\}\) we let \[\begin{aligned}\end{aligned}\] denote the event \(E_1\cap E_2\cap\dots\cap E_k\), , 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}\). Now let \(\cgF\) be a finite family of events, let \(E\in\cgF\) and let \(\cgN\) be a subfamily of \(\cgF-\{E\}\). In the statement of the lemma below, we will say that \(E\) is independent of any event not in \(\cgN\) when \[\begin{aligned}\end{aligned}\] provided \(\cgG\cap\cgN=\emptyset\).

We first state and prove the lemma in asymmetric form. Later, we will give a simpler version which is called the symmetric version.

Now here is the symmetric version.

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\). The proof of this alternate form is just a trivial modification of the argument we have presented here.

Condensed — the full section is in Keller & Trotter, Applied Combinatorics.