On the \(f\)-vectors of cutsets in the Boolean lattice (Q5929842)
From MaRDI portal
scientific article; zbMATH DE number 1586933
Language | Label | Description | Also known as |
---|---|---|---|
English | On the \(f\)-vectors of cutsets in the Boolean lattice |
scientific article; zbMATH DE number 1586933 |
Statements
On the \(f\)-vectors of cutsets in the Boolean lattice (English)
0 references
18 March 2002
0 references
Let \(2^{[n]}\) denote the poset of all subsets of \([n]= \{1,2,\dots, n\}\) ordered by inclusion. A cutset in \(2^{[n]}\) is a subset \(C\) which intersects every maximal chain in \(2^{[n]}\). The \(f\)-vector of \(C\) is an \((n+1)\)-tuple \((f_0, f_1,\dots, f_n)\) with \(f_i= |C\cap \binom{[n]}{i}|\) where \(\binom{[n]}{i}\) denotes the subsets of size \(i\) of \([n]\). The authors define \(\alpha(n)= \inf\{0< \alpha\leq 1\mid (0,\lfloor \alpha \binom{n}{1}\rfloor, \lfloor \alpha\binom{n}{2}\rfloor ,\dots, \lfloor \alpha \binom{n}{n-1} \rfloor, 0)\) is the \(f\)-vector of a cuset in \(2^{[n]}\}\) and prove (Theorem 1) that \(\frac{1}{n}\leq \alpha(n)\leq \frac{3} {2\ln|n/2|}\) for every positive integer \(n> 2\) which implies \(\lim_{n\to\infty} \alpha(n)= 0\). It is conjectured that \(\alpha(n)\leq \frac{c}{n}\) for some fixed constant \(c\).
0 references
Boolean lattice
0 references
profile
0 references
\(f\)-vector
0 references
cutset
0 references
0 references