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 {\mathcal{F} \subset 2^{[n]}} be a family of subsets of {[n] \stackrel{\mathrm{def}}{=} \left\{1, 2, \dots, n\right\}}. We let {d(\mathcal{F})} be the number of disjoint pairs of {\mathcal{F}}: that is, the number of pairs {(A, A') \in \mathcal{F}^2} with {A \cap A' = \emptyset}.

Clearly we have

\displaystyle d(\mathcal{F}) \leq \left\lvert \mathcal{F}\right\rvert^2,

and a natural question is whether this inequality can be substantially improved if {|\mathcal{F}|} is large.

If {n} is even, and we take

\displaystyle \mathcal{F} = \left\{A: A \subset \left\{1, 2, \dots, n/2\right\} \ \text{or} A \subset \left\{n/2 +1 , \dots, n\right\}\right\},

then {| \mathcal{F}| = 2^{n/2 + 1}} while

\displaystyle d(\mathcal{F}) \geq 2 ( 2^{n/2} . 2^{n/2})) = 2^{1+n},

by choosing pairs such that one element is contained in {\left\{1, 2, \dots, n/2\right\}} and the other in {\left\{n/2, \dots, n\right\}}, or vice versa. In particular, we find that d(\mathcal{F}) = \Omega( |\mathcal{F}|^2).

Nonetheless, if {|\mathcal{F}|} grows sufficiently fast, then we have:

Theorem 1 (Alon and Frankl) If we require {|\mathcal{F}| \geq 2^{(1/2 + \delta) n}} for {\delta >0}, then

\displaystyle d(\mathcal{F}) = o( |\mathcal{F}|^2)

as {n \rightarrow \infty}. (more…)