The board / combinatorics / #497
Erdős Problem #497
Dedekind's problem
SOLVED LEANdatabase updated 2026-02-04
Resolved in some way other than a straight proof or disproof — usual for open-ended questions, or for multi-part problems whose parts went different ways. A solution has also been checked by machine, in Lean.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
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\)? 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}}.\]
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved. The authoritative wording is on erdosproblems.com/497.Prizenone
Topicscombinatorics
Statement in LeanFormal Conjectures
Solution in Leanyes
OEISA000372
Original pageerdosproblems.com/497
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.