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?
Maximum intersecting subsets
2 Answers
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}$.
-
0@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$.) ā 2012-09-03
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$.