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

DOI10.1007/PL00009834zbMATH Open0949.05082arXiv1512.02973OpenAlexW2964218233MaRDI QIDQ1586331FDOQ1586331

Authors: Bajnok, Béla, Shahriar Shahriari 

Publication date: 13 November 2000

Published in: Combinatorica (Search for Journal in Brave)

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)$.

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

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

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)

Cited In (6)

• The \(t\)-intersection problem in the truncated Boolean lattice
• Title not available (Why is that?)
• 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)