Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.
share|improve this question
    
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 1

up vote 2 down vote accepted

You are looking for Sperner Families

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.