Tree Posets: Supersaturation, Enumeration, and Randomness
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914091631640576 |
|---|---|
| author | Jiang, Tao Longbrake, Sean Spiro, Sam Yepremyan, Liana |
| author_facet | Jiang, Tao Longbrake, Sean Spiro, Sam Yepremyan, Liana |
| contents | We develop a powerful tool for embedding any tree poset $P$ of height $k$ in the Boolean lattice which allows us to solve several open problems in the area. We show that:
* If $H$ is a family in $B_n$ with $|H|\ge (q-1+\varepsilon){n\choose \lfloor n/2\rfloor}$ for some $q\ge k$, then $H$ contains on the order of as many induced copies of $P$ as is contained in the $q$ middle layers of the Boolean lattice. This generalizes results of Bukh and of Boehnlein and Jiang which guaranteed a single such copy in non-induced and induced settings respectively.
* The number of induced $P$-free families of $B_n$ is $2^{(k-1+o(1)){n\choose \lfloor n/2\rfloor}}$, strengthening recent independent work of Balogh, Garcia, Wigal who obtained the same bounds in the non-induced setting.
* The largest induced $P$-free subset of a $p$-random subset of $B_n$ for $p\gg n^{-1}$ has size at most $(k-1+o(1))p{n\choose \lfloor n/2\rfloor}$, generalizing previous work of Balogh, Mycroft, and Treglown and of Collares and Morris for the case when $P$ is a chain.
All three results are asymptotically tight and give affirmative answers to general conjectures of Gerbner, Nagy, Patkós, and Vizer in the case of tree posets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_11999 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tree Posets: Supersaturation, Enumeration, and Randomness Jiang, Tao Longbrake, Sean Spiro, Sam Yepremyan, Liana Combinatorics 05D05 We develop a powerful tool for embedding any tree poset $P$ of height $k$ in the Boolean lattice which allows us to solve several open problems in the area. We show that: * If $H$ is a family in $B_n$ with $|H|\ge (q-1+\varepsilon){n\choose \lfloor n/2\rfloor}$ for some $q\ge k$, then $H$ contains on the order of as many induced copies of $P$ as is contained in the $q$ middle layers of the Boolean lattice. This generalizes results of Bukh and of Boehnlein and Jiang which guaranteed a single such copy in non-induced and induced settings respectively. * The number of induced $P$-free families of $B_n$ is $2^{(k-1+o(1)){n\choose \lfloor n/2\rfloor}}$, strengthening recent independent work of Balogh, Garcia, Wigal who obtained the same bounds in the non-induced setting. * The largest induced $P$-free subset of a $p$-random subset of $B_n$ for $p\gg n^{-1}$ has size at most $(k-1+o(1))p{n\choose \lfloor n/2\rfloor}$, generalizing previous work of Balogh, Mycroft, and Treglown and of Collares and Morris for the case when $P$ is a chain. All three results are asymptotically tight and give affirmative answers to general conjectures of Gerbner, Nagy, Patkós, and Vizer in the case of tree posets. |
| title | Tree Posets: Supersaturation, Enumeration, and Randomness |
| topic | Combinatorics 05D05 |
| url | https://arxiv.org/abs/2406.11999 |