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
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