A tight, assumption-free probabilistic bound showing that for a large class of random trees—Bienayme-Galton-Watson trees conditioned on size, simply generated trees, and uniform trees with a fixed degree sequence—the product of the tree's height and its width is of order n log n with high probability, uniformly over the offspring distribution. The result ties together the size, height, and width of a random tree and is proved by encoding trees as lattice paths and controlling conditioned random walks along tree spines.
This paper proves assumption-free, non-asymptotic tail bounds on the product of the height and the width of large random trees. For a Bienayme-Galton-Watson (branching-process) tree conditioned to ha…