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

preprint2016arXivOpen access

Abstract

Let La(n,P)La(n,P) be the maximum size of a family of subsets of [n]={1,2,...,n}[n]= \{1,2, ..., n \} not containing PP as a (weak) subposet, and let h(P)h(P) be the length of a longest chain in PP. The best known upper bound for La(n,P)La(n,P) in terms of ∣P∣|P| and h(P)h(P) is due to Chen and Li, who showed that La(n,P)≤1m+1(∣P∣+12(m2+3m−2)(h(P)−1)−1)(n⌊n/2⌋)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≥1m \ge 1. In this paper we show that La(n,P)≤12k−1(∣P∣+(3k−5)2k−2(h(P)−1)−1)(n⌊n/2⌋)La(n,P) \le \frac{1}{2^{k-1}} (|P| + (3k-5)2^{k-2}(h(P)-1) - 1 ) {n \choose {\lfloor n/2\rfloor} } for any fixed k≥2k \ge 2, improving the best known upper bound. By choosing kk appropriately, we obtain that La(n,P)=O(h(P)log⁡2(∣P∣h(P)+2))(n⌊n/2⌋)La(n,P) = O\left( h(P) \log_2\left(\frac{|P|}{h(P)}+2\right) \right) {n \choose \lfloor n/2 \rfloor } as a corollary, which we show is best possible for general PP. 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][n] not containing PP as an induced subposet is O(nc)O(n^c) for every c>12c>\frac{1}{2}.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.