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

الأصل · EN

For integers 0 ≤ m ≤ l ≤ n-m, the truncated Boolean lattice Bₙ(m,l) is the poset of all subsets of [n] = {1, 2,, n} which have size at least m and at most l. C Bₙ(m,l) is a cutset if it meets every chain of length l-m in Bₙ(m,l), and the width of C is the size of the largest antichain in C. We conjecture that for n >> m the minimum width hₙ(m,l) of a cutset in Bₙ(m,l) is Σⱼ ≥ ₀ Δₙ(m-jc) = Δₙ(m)+Δₙ(m-c)+Δₙ(m-2c)+, where c=l-m+1 is the number of level sets in Bₙ(m,l) and Δₙ(k)=n k- n k-1. We establish our conjecture for the cases of "short lattices" (l=m, l=m+1, and l=m+2). For "taller lattices" (l ≥ 2m) our conjecture gives n m - n m-1, independently of l. Our main result is that hₙ(m,l) ≤ n m - n m-1 if l ≥ 2m.