2021/08/19 by József Balogh, Balogh, József, Ryan R. Martin +5 · 1 citation
Computer Science · Mathematics · #05D05 #06A06 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Mathematical Dynamics and Fractals #math.CO #msc:05D05 #msc:06A06 #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2108.08898
13 pages, 3 figures
openalex publication_date 2021/08/19 · arxiv created 2021/11/15 · arxiv updated 2021/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For given posets P and Q and an integer n, the generalized Turán problem for posets, asks for the maximum number of copies of Q in a P-free subset of the n-dimensional Boolean lattice, 2[n]. In this paper, among other results, we show the following: (i) For every n≥ 5, the maximum number of 2-chains in a butterfly-free subfamily of 2[n] is \lceil(n)/(2)\rceil\binomn\lfloor n/2\rfloor. (ii) For every fixed s, t and k, a Ks,t-free family in 2[n] has O(n\binomn\lfloor n/2\rfloor) k-chains. (iii) For every n≥ 3, the maximum number of 2-chains in an N-free family is \binomn\lfloor n/2\rfloor, where N is a poset on 4 distinct elements \p1,p2,q1,q2\ for which p1 < q1, p2 < q1 and p2 < q2. (iv) We also prove exact results for the maximum number of 2-chains in a family that has no 5-path and asymptotic estimates for the number of 2-chains in a family with no 6-path.