# How many subsets are there such that their pairwise intersection is empty?

Let $A$ be a set of $n$ numbers, I need to find the max collection of non empty subset of $A$ such that intersection of any two pair is empty.

To me answer seem $n$, take the example $A = \{1,2,3\}$, there are only three non-empty subsets ({1},{2},{3}) which satisfy the required condition.

In general what is the maximum number of subsets in a collection of subsets such that intersection of any two pair is at most $k$?

• Do you mean the intersection of any pair is empty? – Ross Millikan Nov 10 '17 at 15:56
• @Ross Millikan yes for the first question – user437890 Nov 10 '17 at 15:57
• In your example you should show the "three non-empty subsets", then you could indicate the same for $n$. – Stephen Meskin Nov 10 '17 at 15:57
• @ Stephen Meskin I have asked one more question which is general as compare to first one. – user437890 Nov 10 '17 at 15:59
• For $k \ge n-1$ it is $2^n - 1$ – Stephen Meskin Nov 10 '17 at 16:06

No element of $A$ can be in two of the subsets, or it would be in the intersection of that pair. The approach you hint at, taking all the singletons, is optimal.

• Thanks for the answer. what about the second part of the question? – user437890 Nov 10 '17 at 16:00
• For $k=1$ you can keep all the singletons and add in all the two element subsets, for example. Can you see how this generalizes? – Ross Millikan Nov 10 '17 at 16:03

I think the answer is $\sum_{i=1}^{k+1} \binom {n}{i}$ but a reasonable proof eludes me.
The sum counts all the nonempty subsets of size $\le k+1$. The intersection of any two of them that are distinct can have no more than $k$ elements in common. So the desired number is $\ge$ $\sum_{i=1}^{k+1} \binom {n}{i}$

Going the other way is harder. A collection larger than $\sum_{i=1}^{k+1} \binom {n}{i}$ must contain a subset of size $\ge k+2$. If a set of size $h: n\ge h \ge k+2$ is included then $\binom{h}{k+1}$ sets of size $k+1$ must be excluded. Applying this process one should be able to show that any other collection of non-empty subsets with pairwise intersections of size $\le k$ must contain fewer subsets then $\sum_{i=1}^{k+1} \binom {n}{i}$.

• This seems more like a comment than an answer, until you provide a proof. – Servaes Nov 10 '17 at 17:57
• @ Servaes I can see how you might think that, and I considered it before I posted it. But 1) The OP didn't ask for a proof. 2) The OP may want to prove it her or him self 3) it will make the job of finding a proof easier. 4) I have seen many partial answers on this site with upvotes and some evenhaving been accepted. – Stephen Meskin Nov 10 '17 at 18:27
• This does not provide an answer to the question. To critique or request clarification from an author, leave a comment below their post. - From Review – amWhy Nov 10 '17 at 18:51
• @amWhy I have edited my answer – Stephen Meskin Nov 10 '17 at 21:51