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
we have
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
or 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.
Leave a Reply