On the Minimum Width of a Cutset in the Truncated Boolean Lattice

Abstract

For integers $0\le m\le l\le n-m$, the truncated Boolean lattice ${\mathcal{B}}_n(m,l)$ is the poset of all subsets of $[n]=\{1,2,\dots ,n\}$ which have size at least $m$ and at most $l$. $\mathcal{C}\subseteq {\mathcal{B}}_n(m,l)$ is a {\em cutset} if it meets every chain of length $l-m$ in ${\mathcal{B}}_n(m,l)$, and the {\em width} of $\mathcal{C}$ is the size of the largest antichain in $\mathcal{C}$. We conjecture that for $n>>m$ the minimum width $h_n(m,l)$ of a cutset in ${\mathcal{B}}_n(m,l)$ is ${\Sigma }_{j\ge 0}{\Delta }_n(m-jc)={\Delta }_n(m)+{\Delta }_n(m-c)+{\Delta }_n(m-2c)+\dots$, where $c=l-m+1$ is the number of level sets in ${\mathcal{B}}_n(m,l)$ and ${\Delta }_n(k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)-\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)$. We establish our conjecture for the cases of "short lattices" ($l=m$, $l=m+1$, and $l=m+2$). For "taller lattices" ($l\ge 2m$) our conjecture gives $\left(\genfrac{}{}{0ex}{}{n}{m}\right)-\left(\genfrac{}{}{0ex}{}{n}{m-1}\right)$, independently of $l$. Our main result is that $h_n(m,l)\le \left(\genfrac{}{}{0ex}{}{n}{m}\right)-\left(\genfrac{}{}{0ex}{}{n}{m-1}\right)$ if $l\ge 2m$.