Let $[n] = \{ 1, 2, \ldots, n\}$ and let $2^{ [n]}$ be the collection of all subsets of $[n]$ ordered by inclusion. ${ \cal C} \subseteq 2^{ [n]}$ is a { \em cutset} if it meets every maximal chain in $2^{ [n]}$, and the { \em width} of ${ \cal C} \subseteq 2^{ [n]}$ is the minimum number of chains in a chain decomposition of ${ \cal C}$. Fix $0 \leq m \leq l \leq 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 \leq i \leq 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)$.
Categories: math.CO