Combinatorics and Graph Theory · Problem 1.7.1

Fundamentals — David Guichard

Mathematics — Combinatorics · sperner-theorem-antichains

Problem

Sperner's Theorem (1.7.6) tells us that [63]\left[\begin{smallmatrix}6\\3\end{smallmatrix}\right], with size 20, is the unique largest anti-chain for 2[6]2^{[6]}. The next largest anti-chains of the form [6k]\left[\begin{smallmatrix}6\\k\end{smallmatrix}\right] are [62]\left[\begin{smallmatrix}6\\2\end{smallmatrix}\right] and [64]\left[\begin{smallmatrix}6\\4\end{smallmatrix}\right], with size 15. Find a maximal anti-chain with size larger than 15 but less than 20. (As usual, maximal here means that the anti-chain cannot be enlarged simply by adding elements. So you may not simply use a subset of [63]\left[\begin{smallmatrix}6\\3\end{smallmatrix}\right].)

Related theory

Browse the problem library