An improvement of the general bound on the largest family of subsets avoiding a subposet

Abstract

Let $La(n,P)$ be the maximum size of a family of subsets of $[n]=\{1,2,...,n\}$ not containing $P$ as a (weak) subposet, and let $h(P)$ be the length of a longest chain in $P$. The best known upper bound for $La(n,P)$ in terms of $|P|$ and $h(P)$ is due to Chen and Li, who showed that $La(n,P)\le \frac{1}{m+1}\left(|P|+\frac{1}{2}(m^2+3m-2)(h(P)-1)-1\right)\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ for any fixed $m\ge 1$. In this paper we show that $La(n,P)\le \frac{1}{2^{k-1}}(|P|+(3k-5)2^{k-2}(h(P)-1)-1)\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ for any fixed $k\ge 2$, improving the best known upper bound. By choosing $k$ appropriately, we obtain that $La(n,P)=O\left(h(P){\log }_2\left(\frac{|P|}{h(P)}+2\right)\right)\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$ as a corollary, which we show is best possible for general $P$. We also give a different proof of this corollary by using bounds for generalized diamonds. We also show that the Lubell function of a family of subsets of $[n]$ not containing $P$ as an induced subposet is $O(n^c)$ for every $c>\frac{1}{2}$.

Corrected mistakes, improved the writing. Also added a result about the Lubell function with forbidden induced subposets. The final publication will be available at Springer via http://dx.doi.org/10.1007/s11083-016-9390-3

References in corpus (2)

• Largest family without A union B contained in C intersect D
• Forbidden hypermatrices imply general bounds on induced forbidden subposet problems

Cited by in corpus (4)

• Forbidden induced subposets in the grid
• On forbidden poset problems in the linear lattice
• Largest family without a pair of posets on consecutive levels of the Boolean lattice
• Weak embeddings of posets to the Boolean lattice