ON GENERALIZED TURÁN RESULTS IN HEIGHT TWO POSETS

József Balogh, Ryan R. Martin, Dániel T. Nagy, Balázs Patkós

Research output: Contribution to journalArticlepeer-review

Abstract

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 (Formula Presented). (ii) For every fixed s, t and k, a Ks,t-free family in 2[n] has (Formula Presented) k-chains. (iii) For every n ≥ 3, the maximum number of 2-chains in an N-free family is (Formula Presented) , 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.

Original languageEnglish (US)
Pages (from-to)1483-1495
Number of pages13
JournalSIAM Journal on Discrete Mathematics
Volume36
Issue number2
DOIs
StatePublished - 2022

Keywords

  • butterfly-free poset
  • comparable pairs
  • generalized Turán

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'ON GENERALIZED TURÁN RESULTS IN HEIGHT TWO POSETS'. Together they form a unique fingerprint.

Cite this