Prove that if a collection of subsets of {1,..,n} that each pair of subsets has at least one element in common, there are at most $2^{n-1}$ subsets

Full question: Prove that if a collection of subsets of {1,2,...,n} has the property that each pair of subsets has at least one element in common, then there are at most $2^{n-1}$ subsets in the collection.

I have tried to do an inductive proof as follows:

Base case: When $n = 1$, there is only the set {1}, so $2^{1-1} = 2^0 = 1$ subset in the collection

Inductive step: Let $P(n)$ denote the number of subsets of {1,2,...n} that have at least one element in common, which we will call $A$, is smaller or equal to $2^{n-1}$

Assume $P(n)$ is true. Now we take a look at $P(n+1)$. We can divide subsets of {1,2,...,n+1} into two kind, those containing $n+1$, and those that don't. We know there are $A$ subsets that don't contain $n+1$. For subsets containing $n+1$, we can have $2^n$ subsets. In total, $A + 2^n \geq 2^{n+1-1} = 2^n$, which is obviously incorrect.

I'm not sure if it's possible to do it with an inductive proof, so any kind of proof is welcome. However, it would be great if someone could explain how to do it with the method above, and perhaps point out my mistakes.

• Base step: "There is only the set {1}" No. There is also the set {}. – fleablood Jul 18 '16 at 20:07

An inductive proof is not the way to go.

HINT: Let $[n]=\{1,\ldots,n\}$. If $A\subseteq[n]$, can such a collection contain both $A$ and $[n]\setminus A$?

What I think youâ€™re missing in your attempt to prove the result by induction is that there are many such collections of subsets of $[n]$. For instance, if $n=3$ one such collection is

$$\big\{\{1\},\{1,2\},\{1,2,3\},\{1,2,3,4\}\big\}\;,$$

and another is

$$\big\{\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\big\}\;.$$

Thus, the induction step of a proof by induction would have to start by letting $\mathscr{A}$ be a collection of subsets of $[n+1]$ such that every pair of members of $\mathscr{A}$ have an element in common; the idea would be to use the induction hypothesis to show that $|\mathscr{A}|\le 2^n$.

• Hmm, since the total number of subsets is $2^n$, and a subset and its complement cannot both be in the collection, so the max number of subsets is $2^n/2 = 2^{n-1}$? – Tony Tarng Jul 18 '16 at 20:05
• @Tony: Exactly. – Brian M. Scott Jul 18 '16 at 20:07

Note that there are exactly $2^n$ subsets in total to choose from. It is easy to see how to pick $2^{n-1}$ pairwise intersecting sets because we can just take all subsets of $[n-1]$ and then add $n$ to them.

To see that we cannot have more than $2^{n-1}$ pairwise intersecting sets, begin with a set of $2^{n-1}$ pairwise intersecting sets. For each of those sets, we cannot add its complement, because a set and its complement can never intersect. This gives one "illegal" set for each "legal" one. So we have $2^{n-1}$ legal sets, and $2^{n-1}$ illegal ones. But we only have $2^n$ sets to choose from...

Show the contrapositive: If we have more tan $2^{n-1}$ subsets, then we find two among them that are disjoint.

This can be done by the pigeon-hole principle: There are exactly $2^{n-1}$ subsets $A$ with $n\notin A$. If declare $A$ and $\{1,2,,\ldots,n\}\setminus A$ as a "hole", then we have $2^{n-1}$ holes. Henec if we have more than $2^{n-1}$ subsets - or "pigeons" - then at least one hole must house at least two pigeons.