TY - JOUR
T1 - ON GENERALIZED TURÁN RESULTS IN HEIGHT TWO POSETS
AU - Balogh, József
AU - Martin, Ryan R.
AU - Nagy, Dániel T.
AU - Patkós, Balázs
N1 - \ast Received by the editors November 4, 2021; accepted for publication (in revised form) February 27, 2022; published electronically June 23, 2022. https://doi.org/10.1137/21M1457254 Funding: The first author's research is partially supported by NSF grants DMS-1764123 and RTG DMS-1937241, the Arnold O. Beckman Research Award (UIUC Campus Research Board RB 18132), the Langan Scholar Fund (UIUC), and the Simons Fellowship. The second author's research is partially supported by Simons Foundation Collaboration grants 353292 and 709641. The third author's research is partially supported by NKFIH grants FK 132060, K 132696, and PD 137779 and by the J\a'nos Bolyai Research Fellowship of the Hungarian Academy of Sciences. The fourth author's research is partially supported by NKFIH grants SNN 129364 and FK 132060. \dagger University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA ([email protected]). \ddagger Mathematics, Iowa State University, Ames, IA 50011 USA ([email protected]). \S Alfr\e'd R\e'nyi Institute of Mathematics, Budapest, 1053, Hungary ([email protected], [email protected]).
PY - 2022
Y1 - 2022
N2 - 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.
AB - 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.
KW - butterfly-free poset
KW - comparable pairs
KW - generalized Turán
UR - http://www.scopus.com/inward/record.url?scp=85135219047&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85135219047&partnerID=8YFLogxK
U2 - 10.1137/21M1457254
DO - 10.1137/21M1457254
M3 - Article
AN - SCOPUS:85135219047
SN - 0895-4801
VL - 36
SP - 1483
EP - 1495
JO - SIAM Journal on Discrete Mathematics
JF - SIAM Journal on Discrete Mathematics
IS - 2
ER -