An Improvement of the General Bound on the Largest Family of Subsets Avoiding a Subposet

Grósz, Dániel and Methuku, Abhishek and Tompkins, Casey (2017) An Improvement of the General Bound on the Largest Family of Subsets Avoiding a Subposet. ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 34 (1). pp. 113-125. ISSN 0167-8094

Preview

Text 1408.5783.pdf Download (179kB) | Preview

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 (Formula presented.) for any fixed m ≥ 1. In this paper we show that (Formula presented.) for any fixed k ≥ 2, improving the best known upper bound. By choosing k appropriately, we obtain that (Formula presented.) 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 (Formula presented.) for every (Formula presented.). © 2016 Springer Science+Business Media Dordrecht

Actions (login required)

Edit Item