On Uniform f-vectors of Cutsets in the Truncated Boolean Lattice

Abstract

Let $[n]=\{1,2,\dots ,n\}$ and let $2^{[n]}$ be the collection of all subsets of $[n]$ ordered by inclusion. $\mathcal{C}\subseteq 2^{[n]}$ is a {\em cutset} if it meets every maximal chain in $2^{[n]}$, and the {\em width} of $\mathcal{C}\subseteq 2^{[n]}$ is the minimum number of chains in a chain decomposition of $\mathcal{C}$. Fix $0\le m\le l\le n$. What is the smallest value of $k$ such that there exists a cutset that consists only of subsets of sizes between $m$ and $l$, and such that it contains exactly $k$ subsets of size $i$ for each $m\le i\le l$? The answer, which we denote by $g_n(m,l)$, gives a lower estimate for the width of a cutset between levels $m$ and $l$ in $2^{[n]}$. After using the Kruskal-Katona Theorem to give a general characterization of cutsets in terms of the number and sizes of their elements, we find lower and upper bounds (as well as some exact values) for $g_n(m,l)$.

12 pages