Random trees have height O(n)

We obtain new nonasymptotic tail bounds for the height of uniformly random trees with a given degree sequence, simply generated trees and conditioned Bienaymé 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).