Universal height and width bounds for random trees

DOI10.1214/22-EJP842MaRDI QIDQ2082663

Anna Brandenberger, Jad Hamdan, Louigi Addario-Berry, Céline Kerriou

Publication date: 4 October 2022

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2105.03195

zbMATH Keywords

heightwidthrandom treessimply generated treesGalton-Watson treesBienaymé trees

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Related Items

Multisource invasion percolation on the complete graph

Cites Work

• Unnamed Item
• Scaling limits of random graphs from subcritical classes
• Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation
• Most trees are short and fat
• Sub-Gaussian tail bounds for the width and height of conditioned Galton-Watson trees
• Limit distributions and random trees derived from the birthday problem with unequal probabilities
• On scaling limits of random trees and maps with a prescribed degree sequence
• Limits of random tree-like discrete structures
• Limit theorems for conditioned non-generic Galton-Watson trees
• Decomposition of Lévy trees along their diameter
• Sub-exponential tail bounds for conditioned stable Bienaymé-Galton-Watson trees
• Tail bounds for the height and width of a random tree with a given degree sequence
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• Asymptotics of trees with a prescribed degree sequence and applications