On Uniform f-vectors of Cutsets in the Truncated Boolean Lattice

Original · EN

Let [n] = {1, 2,, n} and let 2[ⁿ] be the collection of all subsets of [n] ordered by inclusion. C 2[ⁿ] is a cutset if it meets every maximal chain in 2[ⁿ], and the width of C 2[ⁿ] is the minimum number of chains in a chain decomposition of 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 gₙ(m,l), gives a lower estimate for the width of a cutset between levels m and l in 2[ⁿ]. 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ₙ(m,l).