Prove that $|\mathcal{F}|\leq 2^{n-1}$

combinatoricsextremal-combinatorics

Let $\mathcal{F}$ be a family of subsets of an $n$-element set $X$. A family is intersecting iff any two of its sets have a non-empty intersection.

How can I prove that if $\mathcal{F}$ is an intersecting family, then $|\mathcal{F}|\leq 2^{n-1}$? How can I show that there is an intersecting family $\mathcal{F}'$ containing $\mathcal{F}$ such that $|\mathcal{F}'| = 2^{n−1}$.

What I've tried: Let $(Y,Z)$ be any partition of $X$. Then at most one of $Y$ and $Z$ can contain an
element of $\mathcal{F}$ . If neither of them does, then both $Y$ and $Z$ are blocking sets. So, if
we let $\mathcal{F}'$ consist of all sets containing a member of $\mathcal{F}$ together with one of each
complementary pair of blocking sets, then $\mathcal{F}'$ contains one of each complementary pair of sets. Furthermore, since $\mathcal{F}$ is intersecting, then any two sets which contain members
of $\mathcal{F}$ must intersect; a set containing a member of $\mathcal{F}$ intersects each blocking
set; and, if we choose the larger of each pair of blocking sets,
then any two of the chosen blocking sets intersect. So we have an intersecting family containing $\mathcal{F}$. But why $|\mathcal{F}'|=2^{n-1}$?

Best Answer

HINT: Write as $V$ the $n$-element set. Then there are $2^n$ subsets of $V$, and furthermore those $2^n$ subsets of $V$ can be partitioned into $2^{n-1}$ pairs $\{S,\bar{S}\}$, where $\bar{S}$ is the complement of $S$. If $\cal{F}$ is intersecting however, then for each $S \in \cal{F}$, its complement $\bar{S}$ in $V$ is not in $\cal{F}$, equivalently, only one of $S$, $\bar{S}$ can be in $\cal{F}$.

Related Question