# Max number of subsets with no inclusion?

What is the largest number of subsets of a given set $S$ of $n$ elements such that:

1. each subset contains at most $k<n$ elements;
2. no subset is included in another one.
-
That depends on $k$. If you forget about $k$, you want all the sets of size $n/2$ (or integer part thereof). –  Gerry Myerson Jun 1 '13 at 11:19
Yes. $k$ is definitively part of the problem. –  Aristide Jun 1 '13 at 11:38
I'm not sure how to prove this but the answer is $$\max\{\binom n j:j\le k\}$$ or if you prefer $\binom n k$ if $k<\lfloor n/2 \rfloor$ and $\binom n {\lfloor(n/2)\rfloor}$ otherwise –  John C Jun 1 '13 at 12:24
You are looking for Sperner Families : en.wikipedia.org/wiki/Sperner_family –  Mark Bennet Jun 1 '13 at 12:56
@MarkBennet: thanks for the reference! If you transform your comment into an answer, I would be glad to accept it. –  Aristide Jun 1 '13 at 17:13

## 1 Answer

You are looking for Sperner Families

I first learned this in Bollobas "The Art of Mathematics" which is full of delightful insights.

-