Random trees have height O(\sqrt{n})
From MaRDI portal
Publication:6505402
arXiv2201.11773MaRDI QIDQ6505402FDOQ6505402
Authors: Louigi Addario-Berry, Serte Donderwinkel 
Abstract: 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 the process settling two conjectures of Janson (2012) 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 with a given number of vertices). 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.
This page was built for publication: Random trees have height $O(\sqrt{n})$
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505402)
