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}$.

Fix such a ${\mathcal{F}}$; we’d like to estimate ${d(\mathcal{F})}$. Alon and Frankl’s strategy is to choose randomly ${t}$ sets ${A_1, \dots, A_t \in \mathcal{F}}$ (for ${t \gg 0}$), and to use two different strategies of estimating the distribution of the number of sets in ${\mathcal{F} }$ disjoint to all the ${A_i}$. One approach will show that it is large, in terms of the number ${d(\mathcal{F})}$. The other will show that it is small.

Strategy 1

Given ${B \in \mathcal{F}}$, we let ${n(B)}$ be the number of sets in ${\mathcal{F}}$ disjoint to ${B}$. Phrased alternatively, if we choose a set in ${\mathcal{F}}$ randomly (all with equal probability) and let ${\mathrm{disj}_B}$ be the event that this randomly chosen set is disjoint from ${B}$, then

$\displaystyle \mathbb{P} (\mathrm{disj}_B) = \mathbb{E}( \chi_{\mathrm{disj}_B} ) = \frac{n(B)}{|\mathcal{F}|}.$

In particular,

$\displaystyle d(\mathcal{F}) = \sum_{B \in \mathcal{F}} n(B).$

Now, if ${A_1, \dots, A_t}$ are chosen randomly, then define ${X}$ to be the random variable whose value is the number of elements in ${\mathcal{F}}$ disjoint from ${A_1, \dots, A_t}$. We have

$\displaystyle X = \sum_B \chi_{\mathrm{disj}^{(t)}_B},$

where ${\mathrm{disj}^{(t)}_B}$ is the event that ${B}$ is disjoint from ${A_1, \dots, A_t}$. Since ${\mathrm{disj}^{(t)}_B}$ is a product of the events ${\mathrm{disj}_B}$ considered above, we have

$\displaystyle \mathbb{E}( \chi_{\mathrm{disj}^{(t)}_B}) = \frac{n(B)^t}{|\mathcal{F}|^t},$

and consequently we get the expectation of ${X}$:

$\displaystyle \mathbb{E}(X) = \sum_B \frac{n(B)^t}{|\mathcal{F}|^t}.$

Since ${t \geq 1}$, we can use convexity of the function ${x \mapsto x^t}$ to bound this below by

$\displaystyle \mathbb{E}(X) = |\mathcal{F} |^{1-t} \sum_B \frac{n(B)^t}{|\mathcal{F}|} \geq |\mathcal{F}|^{1-t} \left( \frac{1}{|\mathcal{F}|} \sum_B n(B) \right)^t = |\mathcal{F}|^{1 - 2t} d(\mathcal{F})^t .$

In particular, if we let ${d(\mathcal{F}) = c_{\mathcal{F}} |\mathcal{F}|^2}$, then we have

$\displaystyle \mathbb{E}(X) \geq c_{\mathcal{F}}^t |\mathcal{F}|. \ \ \ \ \ (1)$

Strategy 2

The next strategy is to argue that ${\mathbb{E}(X)}$ has to be small: namely, if ${t}$ is large and ${A_1, \dots, A_t}$ are chosen randomly, then with high probability

$\displaystyle |A_1 \cup \dots \cup A_t| \geq \frac{n}{2},$

so that with high probability

$\displaystyle X \leq 2^{n/2} \leq 2^{-n\delta} |\mathcal{F}|.$

How can we do this? The event that ${|A_1 \cup \dots \cup A_t| \leq \frac{n}{2} }$ is the union of the events, for each ${S \subset [n]}$ with ${|S| \leq \frac{n}{2}}$, that

$\displaystyle A_1 \cup \dots \cup A_t \subset S,$

so that

$\displaystyle \mathbb{P}( \{ |A_1 \cup \dots \cup A_t| \leq \frac{n}{2} \} ) \leq \sum_{S \subset [n], |S| \leq n/2} \mathbb{P}( \{ A_1 \cup \dots\cup A_t \subset S\}) .$

However, there are at most ${2^{t n/2}}$ possibilities of tuples ${A_1, \dots, A_t}$ whose union is contained in a given ${S}$ with ${|S| = n/2}$, while there are ${\geq 2^{tn(\delta + 1/2)}}$ possibilities of tuples in general. We get that

$\displaystyle \mathbb{P}( \{ |A_1 \cup \dots \cup A_t| \leq \frac{n}{2} \} ) \leq 2^n \frac{2^{t n/2}}{2^{tn( \delta + 1/2)}} = 2^{n ( 1 - t \delta)}.$

Since ${X \geq 2^{n/2}}$ only in case of this event, we can conclude from this:

$\displaystyle \mathbb{P}(X \geq 2^{n/2}) \leq 2^{n ( 1 - t \delta)},$

so that

$\displaystyle \mathbb{E}(X) \leq 2^{n ( 1 - t \delta)} |\mathcal{F}| + 2^{n/2} ( 1- 2^{n ( 1 - t \delta)} ) \leq 2^{n ( 1 - t \delta)} |\mathcal{F}| + 2^{n/2} . \ \ \ \ \ (2)$

Anyway, combining these two estimates (1) and (2) on ${\mathbb{E}(X)}$, we find:

$\displaystyle c_{\mathcal{F}}^t |\mathcal{F}| \leq 2^{n ( 1 - t \delta)} |\mathcal{F}| + 2^{n/2} ,\ \ \ \ \ (3)$

so in particular,

$\displaystyle c_{\mathcal{F}}^t \leq 2^{n(1 - t \delta)} + 2^{-n \delta} .$

As this inequality is valid for any ${t \in \mathbb{N}}$, we take ${t \in [ \frac{1}{\delta}+1 , 2/\delta]}$ but fixed (with ${\delta}$). Then the right-hand-side is ${O( 2^{-n \delta})}$, and we get

$\displaystyle c_{\mathcal{F}} = O( 2^{-n \delta/t} ) = O( 2^{-2n \delta^2}) = o(1),$

as ${n \rightarrow \infty}$ with ${\delta}$ fixed. The ${o(1)}$ is actually exponentially decreasing as ${n \rightarrow \infty}$. More careful analysis can be used to improve these bounds; see either Alon and Spencer’s book or the paper referenced above.