2015/12/09 by Béla Bajnok, Bajnok, Béla, Shahriar Shahriari +1
Mathematics · #05D05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05D05
paper · pdf · doi:10.48550/arxiv.1512.02973
12 pages
arxiv created 2015/12/09 · arxiv updated 2015/12/10
Let [n] = \1, 2, …, n\ and let 2[n] be the collection of all subsets of [n] ordered by inclusion. \cal C ⊆ 2[n] is a \em cutset if it meets every maximal chain in 2[n], and the \em width of \cal C ⊆ 2[n] is the minimum number of chains in a chain decomposition of \cal C. Fix 0 ≤ m ≤ l ≤ 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 ≤ i ≤ l? The answer, which we denote by gn(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 gn(m,l).