2015/12/09 by Béla Bajnok, Bajnok, Béla
Mathematics · #06A07 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:06A07
paper · pdf · doi:10.48550/arxiv.1512.02978
arxiv created 2015/12/09 · arxiv updated 2015/12/10
For integers 0 ≤ m ≤ l ≤ n-m, the truncated Boolean lattice \cal Bn(m,l) is the poset of all subsets of [n] = \1, 2, …, n\ which have size at least m and at most l. \cal C ⊆ \cal Bn(m,l) is a \em cutset if it meets every chain of length l-m in \cal Bn(m,l), and the \em width of \cal C is the size of the largest antichain in \cal C. We conjecture that for n >> m the minimum width hn(m,l) of a cutset in \cal Bn(m,l) is Σj ≥ 0 Δn(m-jc) = Δn(m)+Δn(m-c)+Δn(m-2c)+ …, where c=l-m+1 is the number of level sets in \cal Bn(m,l) and Δn(k)=n \choose k- n \choose 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 \choose m - n \choose m-1, independently of l. Our main result is that hn(m,l) ≤ n \choose m - n \choose m-1 if l ≥ 2m.