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
    0 references
    Boolean lattice
    0 references
    profile
    0 references
    \(f\)-vector
    0 references
    cutset
    0 references

    Identifiers