On the Minimum Width of a Cutset in the Truncated Boolean Lattice

zbMATH Open0953.06008arXiv1512.02978MaRDI QIDQ4489199FDOQ4489199

Authors: Bajnok, Béla 

Publication date: 9 July 2000

Abstract: For integers $0leqmleqlleqn-m$, the truncated Boolean lattice ${calB}_n(m,l)$ is the poset of all subsets of $[n]=1,2,ldots,n$ which have size at least $m$ and at most $l$. $calCsubseteq{calB}_n(m,l)$ is a {em cutset} if it meets every chain of length $l-m$ in ${calB}_n(m,l)$, and the {em width} of $calC$ is the size of the largest antichain in $calC$. We conjecture that for $n>>m$ the minimum width $h_n(m,l)$ of a cutset in ${calB}_n(m,l)$ is $Sigm{a}_{jgeq0}Delt{a}_n(m-jc)=Delt{a}_n(m)+Delt{a}_n(m-c)+Delt{a}_n(m-2c)+dots$, where $c=l-m+1$ is the number of level sets in ${calB}_n(m,l)$ and $Delt{a}_n(k)=nchoosek-nchoosek-1$. We establish our conjecture for the cases of "short lattices" ($l=m$, $l=m+1$, and $l=m+2$). For "taller lattices" ($lgeq2m$) our conjecture gives $nchoosem-nchoosem-1$, independently of $l$. Our main result is that $h_n(m,l)leqnchoosem-nchoosem-1$ if $lgeq2m$.

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

Recommendations

• On uniform \(f\)-vectors of cutsets in the truncated Boolean lattice
• On the n-cutset property
• Minimum cutsets for an element of a Boolean lattice
• Games of chains and cutsets in the Boolean lattice
• A length-width inequality for partially ordered sets with two-element cutsets

zbMATH Keywords

minimum widthcutsettruncated Boolean lattice

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07)

Cited In (9)

• 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
• Minimum cutsets for an element of a Boolean lattice
• Minimum cutsets for an element of a subspace lattice over a finite vector space
• The density of a maximum minimal cut in the subset lattice of a finite set is almost one
• A minimal cutset of the Boolean lattice with almost all members
• On uniform \(f\)-vectors of cutsets in the truncated Boolean lattice
• Note on the \(f\)-vectors of cutsets in the subspace lattice

This page was built for publication: On the Minimum Width of a Cutset in the Truncated Boolean Lattice

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