\(Q _{2}\)-free families in the Boolean lattice (Q766139)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(Q _{2}\)-free families in the Boolean lattice |
scientific article |
Statements
\(Q _{2}\)-free families in the Boolean lattice (English)
0 references
23 March 2012
0 references
Let \(P\) a partially ordered set and \(n\) a positive integer. A family of subsets of \([n]=\{1,2,\ldots,n\}\), taken as a subposet of the \(n\)-dimensional Boolean lattice \(Q_n=(2^{[n]},\subseteq)\), is called \(P\)-free if it does not contain a subposet isomorphic to \(P\). A classical problem of extremal combinatorics is to find the number \(\mathrm{ex}(n,P)\) corresponding to the maximal size of such a \(P\)-free family. When \(P=Q_1\) (i.e., the poset with two elements \(a,b\) with \(a<b\)), this is the problem of finding the maximal size of an antichain, and the answer is given by the Sperner theorem, which asserts that \(\mathrm{ex}(n,Q_1)=\binom{n}{\lfloor n/2 \rfloor}\). The case \(P=Q_2\), the 2-dimensional Boolean lattice, remains open and it is believed that \(\mathrm{ex}(n,Q_2)=2N+o(N)\) with \(N=\binom{n}{\lfloor n/2 \rfloor}\). In this article, the authors prove that \[ 2N-o(N)\leq | \mathcal F | \leq 2.283261N+o(N) \] if \(\mathcal F\) is a \(Q_2\)-free family of subsets of \([n]\). They also improve the upper bound for certain \(Q_2\)-free families (whose elements belong to three layers of \(Q_n\)).
0 references
forbidden poset
0 references
Boolean lattice
0 references
extremal family
0 references