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

preprint2015arXivOpen access

Abstract

Let [n]={1,2,…,n}[n] = \{1, 2, \ldots, n\} and let 2[n]2^{[n]} be the collection of all subsets of [n][n] ordered by inclusion. C⊆2[n]{\cal C} \subseteq 2^{[n]} is a {\em cutset} if it meets every maximal chain in 2[n]2^{[n]}, and the {\em width} of C⊆2[n]{\cal C} \subseteq 2^{[n]} is the minimum number of chains in a chain decomposition of C{\cal C}. Fix 0≤m≤l≤n0 \leq m \leq l \leq n. What is the smallest value of kk such that there exists a cutset that consists only of subsets of sizes between mm and ll, and such that it contains exactly kk subsets of size ii for each m≤i≤lm \leq i \leq l? The answer, which we denote by gn(m,l)g_n(m,l), gives a lower estimate for the width of a cutset between levels mm and ll in 2[n]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)g_n(m,l).

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.