Maximal antichains of subsets I: The shadow spectrum
share
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,…,n}, ordered by inclusion. We characterize all such integers m in the range n⌈ n/2⌉-⌈ n/2⌉^2≤ m≤n⌈ n/2⌉. 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 ℱ of k-sets with |ℱ|=t such that the shadow of ℱ has size s, where the shadow of ℱ is the collection of (k-1)-sets that are contained in at least one member of ℱ. We provide a complete answer for the case t≤ k+1. Moreover, we prove that the largest integer which is not the shadow size of any family of k-sets is √(2)k^3/2+√(8)k^5/4+O(k).
READ FULL TEXT