Let ${A_i, 1 \leq i \leq n}$ be a collection of events in a probability space ${\Omega}$. There are two situations under which we can conclude that

$\displaystyle \bigcup A_i \neq \Omega.$

1. ${\sum \mathbb{P}(A_i) < 1}$.
2. The ${A_i}$ are independent of each other. In this case, the ${\overline{A_i} }$ are independent and ${\mathbb{P} ( \bigcap \overline{A_i}) = \prod \mathbb{P}(\overline{A_i}) >0}$.

There are a number of probabilistic arguments in combinatorics which can be made from the first situation alone. One of the original examples is the problem of bounding below the Ramsey numbers ${R(k, k)}$. By definition, ${R(k, k)}$ is large enough such that any 2-coloring of the edges on a complete graph ${K_{R(k, k)}}$ contains a monochromatic ${k}$-clique ${K_k}$.

In order to show that ${R(k, k)}$ must be larger than some value ${n}$, one chooses a random 2-coloring (with both colors equally likely and the coloring of each edge independent) on the edges of a ${K_n}$. For each ${k}$-subset ${A \subset [n]}$, let ${E_A}$ be the event that ${A}$ is monochromatic under this 2-coloring, so that

$\displaystyle \mathbb{P}(E_A) = 2^{1-\binom{k}{2}}.$

If ${\bigcup_{A: |A| = k} E_A }$ is a proper subset of the probability space, then there is a 2-coloring of ${K_n}$ with no monochromatic ${k}$-clique. In particular, if

$\displaystyle \sum_{A: |A| = k} \mathbb{P}(E_A) = \binom{n}{k} 2^{1-\binom{k}{2}} < 1,$

then we can conclude that there is a 2-coloring of ${K_n}$ without a monochromatic ${K_k}$, so that ${n < R(k, k)}$. One concludes the following lower bound:

Theorem 1 (Erdös) If ${\binom{n}{k} 2^{1-\binom{k}{2}} < 1}$, then ${R(k, k) > n}$.

In such arguments, the individual “bad” events (say, the ${E_A}$) had small probability, and to show that they did not together exhaust the entire probability space, one used the relatively crude bound ${\mathbb{P}( \bigcup A_i) \leq \sum \mathbb{P}(A_i)}$: that is, we used the first of the above two conditions at the beginning of this post. In practice, the events ${A_i}$ are not independent, but a large proportion of them are, and that might suggest the use of a “hybrid” of the two strategies.

The local lemma

The following result is the desired “hybrid”:

Theorem 2 (Lovasz local lemma) Let ${A_i, 1 \leq i \leq n}$ be a collection of events in a probability space ${\Omega}$. Suppose ${\mathbb{P}(A_i) \leq p}$ for all ${i}$, and each ${A_i}$ is mutually independent from a subset of the ${\left\{A_j\right\}}$ excluding at most ${d}$ of them. Then if

$\displaystyle ep(d+1) < 1,$

we have

$\displaystyle \bigcup A_i \neq \Omega.$

Before describing (in a later post) the proof of this result, let’s return to the application of bounding below the ${R(k, k)}$. Again, let’s fix an ${n}$, and let’s try to find conditions under which there exists a 2-coloring of ${K_n}$ with no monochromatic ${k}$-clique. Choose a random 2-coloring of ${K_n}$, defining a probability space ${\Omega}$, and as before let ${E_A }$ (for ${A \subset [n]}$) be the event that ${A}$ is monochromatic. There are ${\binom{n}{k}}$ such events ${E_A}$, each occurring with probability ${p = 2^{1-\binom{k}{2}}}$. Previously, we used the bound

$\displaystyle \mathbb{P}(\bigcup E_A) \leq \sum_A \mathbb{P}(E_A)$

to argue that ${\bigcup E_A \neq \Omega}$.

However, let’s note that ${E_A}$ is mutually independent of the events ${E_B}$ for ${B \cap A = \emptyset}$. In other words, the number of events that ${E_A}$ is not mutually independent of consists of the ${k}$-sets ${B}$ with ${B \cap A \neq \emptyset}$. In fact, we can do a little better: if ${B \cap A}$ consists of one point, then the corresponding cliques to ${A}$ and ${B}$ share no edges, and thus ${E_A}$ is actually mutually independent of all the ${E_B}$, ${|B \cap A | \leq 1}$.

In particular, ${E_A}$ is mutually independent of all but ${\leq \binom{n}{k-2} \binom{k}{2}}$ of the events ${E_B}$. We can take this for ${d}$.

Theorem 3 If

$\displaystyle e \left( \binom{k}{2} \binom{n}{k-2} + 1 \right) 2^{1-\binom{k}{2}} < 1,$

then ${\bigcup E_A \neq \Omega}$, so that ${R(k, k) > n}$.

There is an improvement between the two bounds, since the degree of the polynomial in ${n}$ in the relevant condition has dropped by two. For instance, the first bound that we got without the local lemma says that if ${\binom{n}{k}2^{1-\binom{k}{2}} < 1}$, then ${R(k, k) > n}$. Observe that, asymptotically,

$\displaystyle \binom{n}{k} < \frac{n^k}{k!} \leq \frac{n^k}{(k/e)^k},$

by Stirling’s formula. So the condition ${\binom{n}{k}2^{ 1 - \binom{k}{2}} < 1}$ is implied by

$\displaystyle n^k \leq k! 2^{(k^2 - k)/2 - 1} ,$

or by

$\displaystyle n^k \leq (k/e)^k 2^{(k^2 - k)/2 + 1}, \quad \text{or } \quad n \leq \frac{k}{e \sqrt{2}} 2^{k/2}$

In particular, we get the bound (for ${n}$ large),

$\displaystyle R(k, k) > \frac{k}{e \sqrt{2}}2 ^{k/2}, \ \ \ \ \ (1)$

using the probabilistic argument without the local lemma.

Unfortunately, the local lemma only gives a factor of two improvement. The result derived from it states that the inequality

$\displaystyle e \left( \binom{k}{2} \binom{n}{k-2} + 1 \right) 2^{1-\binom{k}{2}} < 1,$

is enough to imply ${R(k, k) > n}$. Using similar asymptotics, we can bound the left-hand-side by

$\displaystyle e \left( \frac{k^2}{2} \frac{n^{k-2}}{(k/e)^{k-2}} + 1 \right) 2^{1 - (k^2 - k)/2},$

and we will make this ${<1}$ if we can get, for an appropriate constant ${C}$,

$\displaystyle n^{k-2} \leq C (k/e)^{k-4}2^{ (k^2 - k)/2} .$

Taking ${k-2}$st roots, we get that the condition becomes

$\displaystyle R(k, k) > ( 1+ o(1)) \frac{k\sqrt{2}}{e} 2^{k/2} ,\ \ \ \ \ (2)$

which is only twice as good as (1).

Coloring the real line

Let’s consider another application (one of the original ones): coloring the real line. Consider a set ${S \subset \mathbb{R}}$, which is finite. The goal is to give a ${k}$-coloring ${\mathbb{R} \rightarrow [k]}$ such that every subset ${S + x, x \in \mathbb{R}}$, is colorful: that is, all the colors in ${[k]}$ occur. This can be solved using probabilistic methods (if ${k}$ is comfortably large), but note that one needs a tool such as the local lemma: for a random coloring of ${\mathbb{R}}$, the events ${E_x}$ given by “${S+x}$ is not colorful” are large in number, but there are very few dependencies among the events.

Theorem 4 Let ${|S| = m}$. If ${e( m(m-1) + 1) k \left( \frac{k-1}{k} \right)^m < 1}$, then there is a ${k}$-coloring of ${\mathbb{R}}$ such that every translate ${S + x}$ is colorful.

The strategy is to let ${E_x}$ be the “bad” event that ${S+ x}$ fails to be colorful (for a random coloring of ${\mathbb{R}}$). We’d like to show that

$\displaystyle \bigcup_{x \in \mathbb{R}} E_x \neq \Omega,$

where ${\Omega}$ is the corresponding probability space. Since the local lemma is a finitary statement, we will prove the analog for any finite union, and then use a compactness argument to conclude.

Given a random coloring, the probability of ${E_x}$ is bounded by ${k (1 - 1/k)^m}$, since ${E_x}$ involves omitting one of the ${k}$ colors. We take that as our choice of ${p}$. Next, we observe that ${E_x}$ is mutually independent of the ${E_{x'}}$ with ${(S + x) \cap (S + x') = \emptyset}$. The choices of ${x'}$ for which this fails are at most ${m(m-1)}$: when ${x =0}$, the valid ${x'}$ are the pairwise differences ${(S - S ) \setminus \left\{0\right\}}$. Applying the local lemma gives the result.

In other words, we have proved that for any finite subset ${T \subset \mathbb{R}}$, wehave

$\displaystyle \bigcup_{x \in T} E_x \neq \Omega,$

so that there exists a coloring of ${\mathbb{R}}$ such that ${S+x, x \in T}$, is always colorful. Observe that the space of all colorings (that is, ${\mathrm{Fun}(\mathbb{R}, [k])}$, is naturally compact (even profinite), and the condition that ${S+x, x \in T}$ is colorful is a closed condition. Using the finite intersection property, we find that if there is a coloring that makes ${S+ x}$ colorful for ${x}$ in any given finite set, then there is a coloring which makes every ${S+x}$ colorful.