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

Type: 
Lecture
Audience: 
Open to the Public
Thursday, November 6, 2014 - 12:15pm
Add to Calendar
Date: 
Thursday, November 6, 2014 - 12:15pm
Joint work with Daniel Grosz and Casey Tompkins.
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 size of a longest chain in P. Burcsi and Nagy proved an upper bound for La(n,P) in terms of |P| and h(P). This was later improved by 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.
Venue: Rényi Institute