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.

Advertisements