Random trees have height $O(\sqrt{n})$

Louigi Addario-Berry, Serte Donderwinkel

Published 2022-01-27Version 1

We obtain new non-asymptotic tail bounds for the height of uniformly random trees with a given degree sequence, simply generated trees and conditioned Bienaym\'e trees (the family trees of branching processes). In particular, we settle two conjectures of Janson (2012), two conjectures of Addario-Berry, Devroye and Janson (2013), and a conjecture of Addario-Berry (2019). 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 settles a conjecture of Addario-Berry, Donderwinkel, Maazoun and Martin (2021), and can also be used to show that sub-binary random trees are stochastically the tallest trees with a given number of vertices and leaves. Our proofs are based in part on a bijection introduced by Addario-Berry, Donderwinkel, Maazoun and Martin (2021), which can be recast to provide a line-breaking construction of random trees with given vertex degrees.