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
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
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.
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
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
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
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:
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.