# How to prove that $|\mathcal{F}|\leq 2^{n-1}$?

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

• What are your thoughts? What have you tried? Where are you stuck? You need to provide context for your question. Otherwise it just looks like you want somebody to do your homework for you; that's not what this site is for. If you add some appropriate context, we will be happy to help. Jan 7 at 11:19
• @Om3ga You are completely right. I've just added my thought. Thank you. Jan 7 at 11:26
• Think about pairs of sets which are complements to each other. Jan 7 at 11:34
• Thanks for your edit. You meant to say at most one of $Y$ and $Z$ can be an element of $\mathcal{F}$. It looks like the only insight you're missing is (why) $X$ has $2^n$ subsets.
– J.G.
Jan 7 at 11:38
• @hardmath that last comment is not quite right. given an intersecting family $F$, let $G$ be an intersecting family of maximal possible size containing $F$. if $G$ does not have size $2^{n-1}$, then there exists some $A\subseteq X$ such that $A\notin G$ and $A^c\notin G$. by maximality of $G$, neither $G\cup\{A\}$ nor $G\cup\{A^c\}$ is intersecting, so there exist $C,D\in G$ such that $A\cap C=A^c\cap D=\varnothing$. but then $C\cap D=\varnothing$, contradicting that $G$ is intersecting Jan 8 at 19:54

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}$$.
• Thank you very much for the hint. I have a question: how can I define $\mathcal{F}'$ then? Can I define $\mathcal{F}'$ this way: $\mathcal{F}'=\{ S\; |\; \{ S,\bar{S}\}\; \text{is a partition of}\; V$? Then $\mathcal{F}'$ is not intersecting itself. Jan 9 at 10:35
• You mean we need to choose just either $S$ or $\bar{S}$ for which $\{ S,\bar{S}\}$ is a partition of $V$, then since $\mathcal{F}$ is not intersecting, so $\mathcal{F}'$ contains $\mathcal{F}$? Jan 9 at 10:41
• Only one of $S$, $\bar{S}$ can be in $\cal{F}$. So only half of the $2^n$ subsets of $V$ can be in $\cal{F}$.
• Sorry. I understood that $|\mathcal{F}|\leq 2^{n-1}$. But what is $\mathcal{F}'$ containing $\mathcal{F}$? I've taken $\mathcal{F}'$ a family including only one of $S,\bar{S}$ for which $\{ S,\bar{S}\}$ is a partition of $V$ but is $\mathcal{F}'$ intersecting? Jan 12 at 15:46