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

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

  • $\begingroup$ Thanks for the answer. what about the second part of the question? $\endgroup$ – user437890 Nov 10 '17 at 16:00
  • $\begingroup$ 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? $\endgroup$ – 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}$.

  • 5
    $\begingroup$ This seems more like a comment than an answer, until you provide a proof. $\endgroup$ – Servaes Nov 10 '17 at 17:57
  • $\begingroup$ @ 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. $\endgroup$ – Stephen Meskin Nov 10 '17 at 18:27
  • 3
    $\begingroup$ 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 $\endgroup$ – amWhy Nov 10 '17 at 18:51
  • $\begingroup$ @amWhy I have edited my answer $\endgroup$ – Stephen Meskin Nov 10 '17 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy