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.

Advertisements