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