RANDOM TREES HAVE HEIGHT O (√n)

• 成果类型: Article
• 署名作者: Addario-berry, Louigi; Donderwinkel, Serte
• 署名单位: McGill University; University of Groningen; University of Groningen
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/24-AOP1694
• 发表日期: 2024
• 页码: 2238-2280
• 关键词: Random graphs; tail bounds; enumeration; number; LIMITS; width; sle

摘要

We obtain new nonasymptotic tail bounds for the height of uniformly random trees with a given degree sequence, simply generated trees and conditioned Bienaym & eacute; trees (the family trees of branching processes) in the process settling three conjectures of Janson ( Probab. Surv. 9 (2012) 103-252) 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 ( Acta Math. 101 (1959) 141-162) with a given number of vertices). Our proofs are based in part on the Foata-Fuchs bijection between trees and sequences (J. Combin. Theory 8 (1970) 361-375), which can be recast to provide a line-breaking construction of random trees with given vertex degrees ( Electron. Commun. Probab. 28 (2023) 1-13).