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…)