Tight universal bounds on the height times the width of random trees

• 成果类型: Article; Early Access
• 署名作者: Donderwinkel, Serte; Khanfir, Robin
• 署名单位: University of Groningen; University of Groningen; McGill University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051; 1432-2064
• DOI: 10.1007/s00440-025-01462-w
• 发表日期: 2026-01-08
• 关键词: random trees; Bienaym & eacute; -Galton-Watson trees; Simply generated trees; Uniform trees with fixed degrees; height; width; tail bounds

摘要

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.