.png){kind=icon}
.png){kind=icon}
Return
Tight universal bounds on the height times the width of random trees
.png){kind=icon}
PRE
AI
S
R
DOI：10.1007/s00440-025-01462-w.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 & eacute; trees and simply generated trees. We show that for a tree of size n, this product is O(nlogn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(n\log n)$$\end{document} in probability, answering a question by Addario-Berry [2]. The order of this bound is tight in this generality.
Keywords:
Random trees
Bienaym & eacute
-Galton-Watson trees
Simply generated trees
Uniform trees with fixed degrees
Height
Width
Journal
P
IF:
1.6
Papers:
61
Citations:
0
Organization
Cited Papers