I’m TAing a combinatorics course this semester, and as a result I’ve been reading a few books on the subject recently. I’ve in particular been reading Alon and Spencer’s book on the probabilistic method. In this post, I’d like to highlight one of the examples I learned from it; there is a paper by Alon and Frankl where the material originates.
Let be a family of subsets of
. We let
be the number of disjoint pairs of
: that is, the number of pairs
with
.
Clearly we have
and a natural question is whether this inequality can be substantially improved if is large.
If is even, and we take
then while
by choosing pairs such that one element is contained in and the other in
, or vice versa. In particular, we find that
Nonetheless, if grows sufficiently fast, then we have:
Theorem 1 (Alon and Frankl) If we require
for
, then
as
.
Fix such a ; we’d like to estimate
. Alon and Frankl’s strategy is to choose randomly
sets
(for
), and to use two different strategies of estimating the distribution of the number of sets in
disjoint to all the
. One approach will show that it is large, in terms of the number
. The other will show that it is small.
Strategy 1
Given , we let
be the number of sets in
disjoint to
. Phrased alternatively, if we choose a set in
randomly (all with equal probability) and let
be the event that this randomly chosen set is disjoint from
, then
In particular,
Now, if are chosen randomly, then define
to be the random variable whose value is the number of elements in
disjoint from
. We have
where is the event that
is disjoint from
. Since
is a product of the events
considered above, we have
and consequently we get the expectation of :
Since , we can use convexity of the function
to bound this below by
In particular, if we let , then we have
Strategy 2
The next strategy is to argue that has to be small: namely, if
is large and
are chosen randomly, then with high probability
so that with high probability
How can we do this? The event that is the union of the events, for each
with
, that
so that
However, there are at most possibilities of tuples
whose union is contained in a given
with
, while there are
possibilities of tuples in general. We get that
Since only in case of this event, we can conclude from this:
so that
Anyway, combining these two estimates (1) and (2) on , we find:
As this inequality is valid for any , we take
but fixed (with
). Then the right-hand-side is
, and we get
as with
fixed. The
is actually exponentially decreasing as
. More careful analysis can be used to improve these bounds; see either Alon and Spencer’s book or the paper referenced above.
Leave a Reply