2023/08/28 by Patkós, Balázs, Treglown, Andrew
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2308.14863
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. Indeed, 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ós and Vizer [Electronic Journal of Combinatorics, 2021] in these cases. 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.