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

From MaRDI portal





scientific article; zbMATH DE number 1228603
Language Label Description Also known as
English
An extremal problem with excluded subposet in the Boolean lattice
scientific article; zbMATH DE number 1228603

    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