Maximal antichains of subsets I: The shadow spectrum

Jerrold R. Griggs, Thomas Kalinowski, Uwe Leck, Ian T. Roberts, Michael Schmitz

Published 2021-06-04Version 1

Extending a classical theorem of Sperner, we investigate the question for which positive integers $m$ there exists a maximal antichain of size $m$ in the Boolean lattice $B_n$, that is, the power set of $[n]:=\{1,2,\dots,n\}$, ordered by inclusion. We characterize all such integers $m$ in the range $\binom{n}{\lceil n/2\rceil}-\lceil n/2\rceil^2\leq m\leq\binom{n}{\lceil n/2\rceil}$. As an important ingredient in the proof, we initiate the study of an extension of the Kruskal-Katona theorem which is of independent interest. For given positive integers $t$ and $k$, we ask which integers $s$ have the property that there exists a family $\mathcal F$ of $k$-sets with $\lvert\mathcal F\rvert=t$ such that the shadow of $\mathcal F$ has size $s$, where the shadow of $\mathcal F$ is the collection of $(k-1)$-sets that are contained in at least one member of $\mathcal F$. We provide a complete answer for the case $t\leq k+1$. Moreover, we prove that the largest integer which is not the shadow size of any family of $k$-sets is $\sqrt 2k^{3/2}+\sqrt[4]{8}k^{5/4}+O(k)$.