# Maximum intersecting subsets

There are n elements. What is the maximum number of subsets chosen at any one time so that every pair of subsets from collection intersect?

-

This problem is classical, and has a surprisingly trivial solution. Let $[n]=\lbrace 1,\ldots, n\rbrace$. Then $\mathcal{P}([n])$ (the set of all subsets of $[n]$) has size $2^n$. Say that $\mathcal{A}\subset\mathcal{P}([n])$ is intersecting if $A,B\in\mathcal{A}$ implies $A\cap B \ne \emptyset$.

Claim: Every maximal intersecting $\mathcal{A}\subset\mathcal{P}([n])$ contains exactly $2^{n-1}$ sets.

Proof: The upper bound is trivial: if $\mathcal{A}$ contains more than $2^{n-1}$ sets then it contains both $A$ and $A^c$ for some $A\subset[n]$. Now suppose that $\mathcal{A}$ is maximal intersecting, so that we can't add any set to $\mathcal{A}$ without destroying the intersecting property. Certainly $\mathcal{A}$ is an upset, i.e., if $A\in\mathcal{A}$ and $A\subset B$ then $B\in\mathcal{A}$. Suppose $A\notin\mathcal{A}$. Then by maximality there exists $B\in\mathcal{A}$ such that $A\cap B = \emptyset$, i.e., $B\subset A^c$, so $A^c\in\mathcal{A}$.

-
See, e.g., Bollobas Combinatorics. – Sean Eberhard Aug 26 '12 at 19:28
Actually I think the number should be $2^{\max(n-1,0)}$, which is always integer. Think of it! – Marc van Leeuwen Aug 27 '12 at 7:26
@MarcvanLeeuwen If $n=0$ shouldn't the maximum be $0$ actually? I guess it depends on what you mean by a "pair" of subsets: can you take the same set twice? (Note $\emptyset\cap\emptyset=\emptyset$.) – Sean Eberhard Sep 3 '12 at 15:13

As Sean Eberhard says, if $\mathcal{A}$ contains more than $2^{n−1}$ subsets of $[n]$ then it contains at least one pair of complementary subsets, so $2^{n−1}$ is an upper bound for $n\ge 1$.

It is easy to construct an example meeting this upper bound: simply let $\mathcal{B}\subset\mathcal{P}([n])$ contain just those subsets of $[n]$ which have $n$ as an element. $\mathcal{B}$ clearly contains $2^{n-1}$ subsets of $[n]$ and the intersection of any positive number of them contains $n$.

-