全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
Mathematics  2014 

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

Full-Text   Cite this paper   Add to My Lib

Abstract:

Let $La(n,P)$ be the maximum size of a family of subsets of $[n]= \{1,2, \ldots, n \}$ not containing $P$ as a (weak) subposet, and let $h(P)$ be the length of a longest chain in $P$. The best known upperbound 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) {\binom {n} {\lfloor n/2 \rfloor}}$ for any fixed $m \ge 1$. In this paper we show that $La(n,P) \le \frac{1}{2^{k-1}} \left(|P| + (3k-5)2^{k-2}(h(P)-1) - 1 \right) {n \choose \left\lfloor n/2\right\rfloor }$ for any fixed $k \ge 2$, thereby 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) {n \choose \left\lfloor \frac{n}{2}\right\rfloor }$ 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.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133