Random trees have height $O(\sqrt{n})$
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929267839860736 |
|---|---|
| author | Addario-Berry, Louigi Donderwinkel, Serte |
| author_facet | Addario-Berry, Louigi Donderwinkel, Serte |
| contents | We obtain new non-asymptotic tail bounds for the height of uniformly random trees with a given degree sequence, simply generated trees and conditioned Bienaymé trees (the family trees of branching processes), in the process settling three conjectures of Janson (2012) and answering several other questions from the literature.
Moreover, we define a partial ordering on degree sequences and show that it induces a stochastic ordering on the heights of uniformly random trees with given degree sequences. The latter result can also be used to show that sub-binary random trees are stochastically the tallest trees with a given number of vertices and leaves (and thus that random binary trees are the stochastically tallest random homeomorphically irreducible trees with a given number of vertices).
Our proofs are based in part on the bijection between trees and sequences introduced by Foata and Fuchs (1970), which can be recast to provide a line-breaking construction of random trees with given vertex degrees as shown in Addario-Berry, Blanc-Renaudie, Donderwinkel, Maazoun and Martin (2023). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2201_11773 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Random trees have height $O(\sqrt{n})$ Addario-Berry, Louigi Donderwinkel, Serte Probability Combinatorics 60C05, 6J80, 05C05 We obtain new non-asymptotic tail bounds for the height of uniformly random trees with a given degree sequence, simply generated trees and conditioned Bienaymé trees (the family trees of branching processes), in the process settling three conjectures of Janson (2012) and answering several other questions from the literature. Moreover, we define a partial ordering on degree sequences and show that it induces a stochastic ordering on the heights of uniformly random trees with given degree sequences. The latter result can also be used to show that sub-binary random trees are stochastically the tallest trees with a given number of vertices and leaves (and thus that random binary trees are the stochastically tallest random homeomorphically irreducible trees with a given number of vertices). Our proofs are based in part on the bijection between trees and sequences introduced by Foata and Fuchs (1970), which can be recast to provide a line-breaking construction of random trees with given vertex degrees as shown in Addario-Berry, Blanc-Renaudie, Donderwinkel, Maazoun and Martin (2023). |
| title | Random trees have height $O(\sqrt{n})$ |
| topic | Probability Combinatorics 60C05, 6J80, 05C05 |
| url | https://arxiv.org/abs/2201.11773 |