Tight universal bounds on the height times the width of random trees

2024/12/31 by Donderwinkel, Serte, Khanfir, Robin
#05C05 #60C05 #60J80 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2501.00458

Abstract

We obtain assumption-free, non-asymptotic, uniform bounds on the product of the height and the width of uniformly random trees with a given degree sequence, conditioned Bienaymé trees and simply generated trees. We show that for a tree of size n, this product is O(n log n) in probability, answering a question by Addario-Berry (2019). The order of this bound is tight in this generality.

Related

• Universal height and width bounds for random trees
• Random trees have height O(√(n))
• Tail bounds for the height and width of a random tree with a given\n degree sequence
• Upper Bounds on the Average Height of Random Binary Trees
• Random increasing plane trees: asymptotic enumeration of vertices by distance from leaves