On Uniform f-vectors of Cutsets in the Truncated Boolean Lattice |
| |
Authors: | Béla Bajnok Shahriar Shahriari |
| |
Institution: | (1) Gettysburg College, Mathematics; Box 402 Gettysburg, PA 17325, USA; E-mail: bbajnok@gettysburg.edu, US;(2) Pomona College; Claremont, CA 91711, USA; E-mail: sshahriari@pomona.edu, US |
| |
Abstract: | and let be the collection of all subsets of n] ordered by inclusion. is a cutset if it meets every maximal chain in , and the width of is the minimum number of chains in a chain decomposition of . Fix . What is the smallest value of 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 ? The answer, which we denote by , gives a lower estimate for the width of a cutset between levels m and l in . 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 .
Received September 4, 1997 |
| |
Keywords: | AMS Subject Classification (1991) Classes: 05D05 06A07 06E05 06B05 |
本文献已被 SpringerLink 等数据库收录! |
|