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

Question

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.

Answer 1

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$.

Answer 2

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...

Answer 3

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.

Answer 4

Let $m$ be the maximum number of subsets in the collection of $\{1,2,...,n\}$.

Prove $m\ge n$: We can select all subsets of $\{1,2,...,n-1\}$ and plus $\{n\}$ to each of them. Then we have $2^{n-1}$ subsets.

Prove $m\le n$: For each subset selected, we can't have its complement selected, we can't have more than $2^{n-1}$ subsets.

So we prove $m=2^{n-1}$. There are at most $2^{n−1}$ subsets in the collection.