Article ID Journal Published Year Pages File Type
4655136 Journal of Combinatorial Theory, Series A 2015 17 Pages PDF
Abstract
Let F be a family of subsets of {1,…,n}. We say that F is P-free if the inclusion order on F does not contain P as an induced subposet. The Turán function of P, denoted La⁎(n,P), is the maximum size of a P-free family of subsets of {1,…,n}. We show that La⁎(n,P)≤(4r+O(r))(n⌊n/2⌋) if P is an r-element poset of height at most 2. We also show that La⁎(n,Sr)=(r+O(r))(n⌊n/2⌋) where Sr is the standard example on 2r elements, and that La⁎(n,2[2])≤(2.583+o(1))(n⌊n/2⌋), where 2[2] is the 2-dimensional Boolean lattice.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,