Let $\mathcal F$ be a family of subsets of a set consisting of $n$ elements so that no element of $\mathcal F$ is a subset of another element. Prove that $\mathcal F$ can have at most $$\binom{n}{\Big\lfloor\frac{n}{2}\Big\rfloor}.$$

Are these partitions? I suspected I could use induction, but it isn't really clear.

Award task, Socialist Republic Croatia, Yugoslavia 1973

  • $\begingroup$ Sure, I'll do that. $\endgroup$ – Orchid_2.718281828 Nov 10 '19 at 20:22
  • $\begingroup$ @ViktorGlombik I didn't want to write anything on my own because I translated it literally not to write anything wrong since I don't know if I have covered enough theory to conclude. $\endgroup$ – Orchid_2.718281828 Nov 10 '19 at 20:26
  • $\begingroup$ I mean, this is obvious, but I followed the author... $\endgroup$ – Orchid_2.718281828 Nov 10 '19 at 20:28
  • $\begingroup$ @ViktorGlombik I don't at all see how this would be equivalent to the sets in $\mathcal{F}$ being mutually disjoint. $\endgroup$ – Morgan Rodgers Nov 10 '19 at 20:45
  • $\begingroup$ Oh, now I see how much I still have to learn. $\endgroup$ – Orchid_2.718281828 Nov 10 '19 at 20:46

This is just Sperner theorem.


Your Answer

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

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