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

antichainBoolean latticecutsetKruskal-Katona theoremprofile

Mathematics Subject Classification ID

Extremal set theory (05D05) Combinatorics of partially ordered sets (06A07) 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)$.

Review text

Let \(2^{[n]}\) be the Boolean lattice, i.e. the lattice of subsets of \([n]:=\{1,\dots,n\}\), ordered by inclusion. A family \(\mathcal C\subseteq 2^{[n]}\) is called a cutset if it meets every maximal chain in \(2^{[n]}\). The profile of \(\mathcal C\) is a vector \(f=(f_0,\dots,f_n)\) where \(f_i:=|\{X\in \mathcal C:|X|=i\}|\). Let \(g_n(m,\ell)\) be the smallest value of \(k\) for which the \((n+1)\)-tuple \((f_0,\dots, f_n)\), defined by \(f_i=k\) if \(m\leq i\leq \ell\) and 0 otherwise, can be the profile of a cutset in \(2^{[n]}\). The authors prove: \[ \begin{alignedat}{2} g_n(m,m+1) &=\begin{pmatrix} n-1 \\ m\end{pmatrix} , \quad & & 0\leq m\leq n-1, \\ g_n(m,m+2) & = \sum^m_{j=0} \begin{pmatrix} n-2j-2\\ m-j \end{pmatrix}, \quad & & 0\leq m\leq \frac n2 -1 . \end{alignedat} \] Moreover, if \(\frac nm\) is sufficiently large, \[ \begin{gathered} \begin{pmatrix} n-2\\ m \end{pmatrix} <g_n(m,\ell) \leq \sum^m_{j=0} \begin{pmatrix} n-2j-2\\ m-j \end{pmatrix} , \quad m+2\leq \ell \leq n-m-1, \\ \begin{pmatrix} n-3\\ m \end{pmatrix} <g_n(m,n-m)\leq \sum^m_{j=0} \begin{pmatrix} n-2j-3\\m-j\end{pmatrix}. \end{gathered} \] These numerical results are derived from a qualitativ description of the possible cutset-profiles using compression and canonical forms. The authors conjecture that for sufficiently large \(\frac nm\) \[ g_n(m,\ell) = \begin{pmatrix} n\\ m \end{pmatrix} -\begin{pmatrix} n\\ m-1\end{pmatrix}, \quad 2m\leq \ell\leq n-m-1, \] \[ g_n(m,n-m)=\begin{pmatrix} n-1\\ m\end{pmatrix} -\begin{pmatrix} n-1\\ m-1\end{pmatrix} . \]

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
• On the Minimum Width of a Cutset in the Truncated Boolean Lattice
• Edge‐cutsets in the directed hypercube
• 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

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)