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 . (more…)