Let be a collection of events in a probability space . There are two situations under which we can conclude that
- The are independent of each other. In this case, the are independent and .
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 . By definition, is large enough such that any 2-coloring of the edges on a complete graph contains a monochromatic -clique .
In order to show that must be larger than some value , one chooses a random 2-coloring (with both colors equally likely and the coloring of each edge independent) on the edges of a . For each -subset , let be the event that is monochromatic under this 2-coloring, so that
If is a proper subset of the probability space, then there is a 2-coloring of with no monochromatic -clique. In particular, if
then we can conclude that there is a 2-coloring of without a monochromatic , so that . One concludes the following lower bound:
Theorem 1 (Erdös) If , then .
In such arguments, the individual “bad” events (say, the ) had small probability, and to show that they did not together exhaust the entire probability space, one used the relatively crude bound : that is, we used the first of the above two conditions at the beginning of this post. In practice, the events 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 be a collection of events in a probability space . Suppose for all , and each is mutually independent from a subset of the excluding at most of them. Then if
Before describing (in a later post) the proof of this result, let’s return to the application of bounding below the . Again, let’s fix an , and let’s try to find conditions under which there exists a 2-coloring of with no monochromatic -clique. Choose a random 2-coloring of , defining a probability space , and as before let (for ) be the event that is monochromatic. There are such events , each occurring with probability . Previously, we used the bound
to argue that .
However, let’s note that is mutually independent of the events for . In other words, the number of events that is not mutually independent of consists of the -sets with . In fact, we can do a little better: if consists of one point, then the corresponding cliques to and share no edges, and thus is actually mutually independent of all the , .
In particular, is mutually independent of all but of the events . We can take this for .
Theorem 3 If
then , so that .
There is an improvement between the two bounds, since the degree of the polynomial in in the relevant condition has dropped by two. For instance, the first bound that we got without the local lemma says that if , then . Observe that, asymptotically,
by Stirling’s formula. So the condition is implied by
In particular, we get the bound (for large),
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
is enough to imply . Using similar asymptotics, we can bound the left-hand-side by
and we will make this if we can get, for an appropriate constant ,
Taking st roots, we get that the condition becomes
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 , which is finite. The goal is to give a -coloring such that every subset , is colorful: that is, all the colors in occur. This can be solved using probabilistic methods (if is comfortably large), but note that one needs a tool such as the local lemma: for a random coloring of , the events given by “ is not colorful” are large in number, but there are very few dependencies among the events.
Theorem 4 Let . If , then there is a -coloring of such that every translate is colorful.
The strategy is to let be the “bad” event that fails to be colorful (for a random coloring of ). We’d like to show that
where 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 is bounded by , since involves omitting one of the colors. We take that as our choice of . Next, we observe that is mutually independent of the with . The choices of for which this fails are at most : when , the valid are the pairwise differences . Applying the local lemma gives the result.
In other words, we have proved that for any finite subset , wehave
so that there exists a coloring of such that , is always colorful. Observe that the space of all colorings (that is, , is naturally compact (even profinite), and the condition that is colorful is a closed condition. Using the finite intersection property, we find that if there is a coloring that makes colorful for in any given finite set, then there is a coloring which makes every colorful.