Problem Statement
How many antichains in $[n]$ are there? That is, how many families of subsets of $[n]$ are there such that, if $\mathcal{F}$ is such a family and $A,B\in \mathcal{F}$, then $A\not\subseteq B$?
Categories:
Combinatorics
Progress
Sperner's theorem states that $\lvert \mathcal{F}\rvert \leq \binom{n}{\lfloor n/2\rfloor}$. This is also known as Dedekind's problem.Resolved by Kleitman [Kl69], who proved that the number of such families is\[2^{(1+o(1))\binom{n}{\lfloor n/2\rfloor}}.\]
Source: erdosproblems.com/497 | Last verified: January 15, 2026