Minimum Weight Flat Antichains of Subsets

Abstract

Building on classical theorems of Sperner and Kruskal-Katona, we investigate antichains $\mathcal{F}$ in the Boolean lattice $B_n$ of all subsets of $[n]:=\{1,2,\dots ,n\}$, where $\mathcal{F}$ is flat, meaning that it contains sets of at most two consecutive sizes, say $\mathcal{F}=\mathcal{A}\cup \mathcal{B}$, where $\mathcal{A}$ contains only $k$-subsets, while $\mathcal{B}$ contains only $(k-1)$-subsets. Moreover, we assume $\mathcal{A}$ consists of the first $m$ $k$-subsets in squashed (colexicographic) order, while $\mathcal{B}$ consists of all $(k-1)$-subsets not contained in the subsets in $\mathcal{A}$. Given reals $\alpha ,\beta >0$, we say the weight of $\mathcal{F}$ is $\alpha \cdot |\mathcal{A}|+\beta \cdot |\mathcal{B}|$. We characterize the minimum weight antichains $\mathcal{F}$ for any given $n,k,\alpha ,\beta$, and we do the same when in addition $\mathcal{F}$ is a maximal antichain. We can then derive asymptotic results on both the minimum size and the minimum Lubell function.