On uniform f-vectors of cutsets in the truncated Boolean lattice

DOI10.1007/PL00009834MaRDI QIDQ1586331zbMATH OpenOpenAlexFDO

Authors Bajnok, Béla, Shahriar Shahriari

Publication date 13 November 2000

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.02973

zbMATH Keywords

profileantichainKruskal-Katona theoremBoolean latticecutset

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Extremal set theory (05D05) Structure theory of Boolean algebras (06E05)

Abstract: Let $[n]=1,2,ldots,n$ and let $2^{[n]}$ be the collection of all subsets of $[n]$ ordered by inclusion. $calCsubseteq{2}^{[n]}$ is a {em cutset} if it meets every maximal chain in $2^{[n]}$, and the {em width} of $calCsubseteq{2}^{[n]}$ is the minimum number of chains in a chain decomposition of $calC$. Fix $0leqmleqlleqn$. 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 $mleqileql$? The answer, which we denote by $g_n(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 $g_n(m,l)$.

Recommendations

• On the \(f\)-vectors of cutsets in the Boolean lattice
• Cutsets of Boolean lattices
• Note on the \(f\)-vectors of cutsets in the subspace lattice
• On the Minimum Width of a Cutset in the Truncated Boolean Lattice
• Cutsets and anti-chains in linear lattices
• The \(t\)-intersection problem in the truncated Boolean lattice
• Minimum cutsets for an element of a Boolean lattice
• Minimum cutsets for an element of a subspace lattice over a finite vector space
• Cutset condition for geometric lattices
• A Cheeger cut for uniform hypergraphs

Cited in

(6)

• The \(t\)-intersection problem in the truncated Boolean lattice
• scientific article; zbMATH DE number 2230313 (Why is no real title available?)
• On the \(f\)-vectors of cutsets in the Boolean lattice
• Cutsets and anti-chains in linear lattices
• On the Minimum Width of a Cutset in the Truncated Boolean Lattice
• Edge‐cutsets in the directed hypercube

This page was built for publication: On uniform \(f\)-vectors of cutsets in the truncated Boolean lattice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1586331)