2014/08/04 by Linyuan Lü, Lu, Linyuan, Kevin G. Milans +1 · 1 citation
Computer Science · Mathematics · #05D05 #06A07 #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1408.0646
openalex publication_date 2014/08/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 π^*(n,P), is the maximum size of a P-free family of subsets of \1,…,n\. We show that π^*(n,P) ≤ (4r + O(√(r)))\binomnn/2 if P is an r-element poset of height at most 2. We also show that π^*(n,Sr) = (r+O(√(r)))\binomnn/2 where Sr is the standard example on 2r elements, and that π^*(n,B2) ≤ (2.583+o(1))\binomnn/2, where B2 is the 2-dimensional Boolean lattice.