Exercise 6.5.2 of the Probabilistic Methods(4th Edtion) by Alon and Spencer

Question

A family of subsets $\mathcal{G}$ is called intersecting if $G_{1} \cap G_{2} \neq \emptyset$ for all $G_{1}, G_{2} \in \mathcal{G}$. Let $\mathcal{F}_{1}, \mathcal{F}_{2}, \ldots, \mathcal{F}_{k}$ be $k$ intersecting families of subsets of $\{1,2, \ldots, n\}$. Prove that $$ \left|\bigcup_{i=1}^{k} \mathcal{F}_{i}\right| \leq 2^{n}-2^{n-k} . $$

Answer 1

Here is a way to see that $|\mathcal{F}| \le 2^{n-1}$ without invoking Erdős-Ko-Rado. If $\mathcal{F}$ contains more than half of all possible sets, it must contain some set and its complement, by the pigeonhole principle. But no set intersects its complement, by definition.

As an aside, I do not believe that Erdős-Ko-Rado works outright in this situation, because of the condition that $n \ge 2k$. For larger $k$, we can actually have an intersecting family of size $\binom{n}{k}$ (i.e. when $k > \frac{n}{2}$, all sets of size $k$ intersect all other such sets). So, the bound above would look like $$|\mathcal{F}| \le \binom{n-1}{0} + \binom{n-1}{1} + \ldots + \binom{n-1}{n/2-1} + \binom{n}{n/2+1}+\binom{n}{n/2+2}+\ldots+\binom{n}{n}$$ This sum is strictly larger than $2^{n-1}$, so we do not attain the desired bound this way.

Answer 2

Choose $S\in 2^{\{1,\cdots,n\}}$ uniformly at random, then

$$ \begin{align} \frac{|\bigcup_{i=1}^{k} \mathcal{F}_{i}|}{2^n}&=P(S\in \bigcup_{i=1}^{k} \mathcal{F}_{i}) \\ &=1-P(\bigvee_{i=1}^{k}S\notin \mathcal{F}_i) \\ &\le 1-\prod_{i=1}^{k} P(S\notin \mathcal{F}_i) \end{align} $$

The last inequation holds by Harris inequality since each event $S\notin \mathcal{F}_i$ is an decreasing event(deleting some subset(s) from an intersecting family will not harm its being intersecting). Then the original proposition is equivalent to
$$P(S\in \mathcal{F}_i)\le \frac{1}{2}$$

To prove above inequation, we need the Erdőss-Ko-Rado theorem(see in the page right before Chapter 2 in the same book or wiki):

Suppose $n \geq 2 k$, and let $\mathcal{F}$ be an intersecting family of $k$ -element subsets of an $n$ -set, for definiteness $\{0, \ldots, n-1\} .$ The Erdőss-Ko-Rado theorem is that $|\mathcal{F}| \leq\left(\begin{array}{c}n-1 \\ k-1\end{array}\right)$.

The $\mathcal{F}_i$ in the original problem can contain subsets of size ranging from $1$ to $n$, and subsets of fixed size in $\mathcal{F}_i$ can also form an intersecting family, hence $$|\mathcal{F}_i|\le \left(\begin{array}{c}n-1 \\ 0\end{array}\right)+\cdots + \left(\begin{array}{c}n-1 \\ n-1\end{array}\right) = 2^{n-1}$$

Thus we have $P(S\in \mathcal{F}_i)\le \frac{|\mathcal{F}_{i}|}{2^{n}} \le \frac{1}{2}$. $\tag*{$\blacksquare$}$

Notes: I was stucked on this exercise untill I saw the Erdőss-Ko-Rado theorem in this book. And I don't think I can solve it without knowing this theorem. So any solution without using the Erdőss-Ko-Rado theorem will be appreciated.