An extremal problem with excluded subposet in the Boolean lattice (Q1272945)

From MaRDI portal
scientific article
Language Label Description Also known as
English
An extremal problem with excluded subposet in the Boolean lattice
scientific article

    Statements

    An extremal problem with excluded subposet in the Boolean lattice (English)
    0 references
    0 references
    0 references
    2 August 1999
    0 references
    Let \(F\) be a family of subsets of \(\{1,\dots,n\}\) with the following property: There are not \(A_1,\dots,A_u\), \(B_1, \dots,B_v\in F\) such that \(A_1\subset \cdots\subset A_u\), \(A_u\subset B_1,\dots, A_u\subset B_v\). Let \(f_n(u,v)\) be the maximum size of a family with this property. Let \((b_0, \dots, b_n)\) be the sequence of binomial coefficients in decreasing order, i.e. \[ \{b_0,\dots,b_n\}=\left\{{n\choose 0},\dots,{n\choose n}\right\},\quad b_0\geq b_1\geq\cdots\geq b_n. \] It is proved that for \(u\geq 1\) and \(v\geq 2\) \[ b_0+ \cdots +b_{u-1}+b_u/ \left\lceil {n\over v-1}\right \rceil\leq f_n(u,v)\leq b_0+ \cdots+ b_{u-1}+ b_u\left({2(v-1) {u+v-2\choose 2} \over n}+o \left({1\over n}\right) \right). \]
    0 references
    Boolean lattice
    0 references
    Sperner's theorem
    0 references
    excluded subposet
    0 references
    fork
    0 references
    0 references

    Identifiers