On Some Extremal and Probabilistic Questions for Tree Posets
Open Access
- 12 January 2024
- journal article
- research article
- Published by The Electronic Journal of Combinatorics in The Electronic Journal of Combinatorics
- Vol. 31 (1) , P1.19
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ós 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], andCollares 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.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- Extremal Finite Set Theory2018
- Subsets of posets minimising the number of chainsTransactions of the American Mathematical Society, 2018
- Random and deterministic versions of extremal poset problems2018
- A random version of Sperner's theoremJournal of Combinatorial Theory, Series A, 2014
- The partition method for poset-free familiesJournal of Combinatorial Optimization, 2012
- On Families of Subsets With a Forbidden SubposetCombinatorics, Probability and Computing, 2009
- Set Families with a Forbidden SubposetThe Electronic Journal of Combinatorics, 2009
- Maximum Antichains in Random Subsets of a Finite SetJournal of Combinatorial Theory, Series A, 2000
- On Dedekind's Problem: The Number of Monotone Boolean FunctionsProceedings of the American Mathematical Society, 1969
- Ein Satz ber Untermengen einer endlichen MengeMathematische Zeitschrift, 1928