On Some Extremal and Probabilistic Questions for Tree Posets

Patkós, Balázs and Treglown, A. (2024) On Some Extremal and Probabilistic Questions for Tree Posets. ELECTRONIC JOURNAL OF COMBINATORICS, 31 (1). ISSN 1097-1440

Preview

Text 12344-PDFfile-48080-2-10-20240116.pdf - Published Version Available under License Creative Commons Attribution. Download (400kB) | Preview

Abstract

Given two posets P, Q we say that Q is P -free if Q does not contain a copy of P . The size of the largest P -free family in 2[n], denoted by La(n, P ), has been extensively studied since the 1980s. We consider several related problems. For posets P whose Hasse diagrams are trees and have radius at most 2, we prove that there are 2(1+o(1))La(n,P ) P -free families in 2[n], thereby confirming a conjecture of Gerbner, Nagy, Patk´os and Vizer [Electronic Journal of Combinatorics, 2021] in this case. For such P we also resolve the random version of the P -free problem, thus generalising the random version of Sperner’s theorem due to Balogh, Mycroft and Treglown [Journal of Combinatorial Theory Series A, 2014], and Collares Neto and Morris [Random Structures and Algorithms, 2016]. Additionally, we make a general conjecture that, roughly speaking, asserts that subfamilies of 2[n] of size sufficiently above La(n, P ) robustly contain P , for any poset P whose Hasse diagram is a tree.

Actions (login required)

Edit Item