Tight universal bounds on the height times the width of random trees
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913632055459840 |
|---|---|
| author | Donderwinkel, Serte Khanfir, Robin |
| author_facet | Donderwinkel, Serte Khanfir, Robin |
| contents | We obtain assumption-free, non-asymptotic, uniform bounds on the product of the height and the width of uniformly random trees with a given degree sequence, conditioned Bienaymé trees and simply generated trees. We show that for a tree of size $n$, this product is $O(n \log n)$ in probability, answering a question by Addario-Berry (2019). The order of this bound is tight in this generality. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_00458 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tight universal bounds on the height times the width of random trees Donderwinkel, Serte Khanfir, Robin Probability Combinatorics 60C05, 60J80, 05C05 We obtain assumption-free, non-asymptotic, uniform bounds on the product of the height and the width of uniformly random trees with a given degree sequence, conditioned Bienaymé trees and simply generated trees. We show that for a tree of size $n$, this product is $O(n \log n)$ in probability, answering a question by Addario-Berry (2019). The order of this bound is tight in this generality. |
| title | Tight universal bounds on the height times the width of random trees |
| topic | Probability Combinatorics 60C05, 60J80, 05C05 |
| url | https://arxiv.org/abs/2501.00458 |