The saturation spectrum for antichains of subsets

Abstract

Extending a classical theorem of Sperner, we characterize the integers $m$ such that 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. 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 $|\mathcal{F}|=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 $t⩽k+1$. Moreover, we prove that the largest integer which is not the shadow size of any family of $k$-sets is $\sqrt{2}{k}^{3/2}+\sqrt[4]{8}{k}^{5/4}+O(k)$.

This is a merger of arXiv:2106.02226v2 with arXiv:2106.02230