Tail bounds for the height and width of a random tree with a given degree sequence

Fix a sequence c = ( c 1 ,…, c n ) of non‐negative integers with sum n − 1. We say a rooted tree T has child sequence c if it is possible to order the nodes of T as v 1 ,…, v n so that for each 1 ≤ i ≤ n , v i has exactly c i children. Let \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}${\mathcal T}$\end{document} be a plane tree drawn uniformly at random from among all plane trees with child sequence c . In this note we prove sub‐Gaussian tail bounds on the height (greatest depth of any node) and width (greatest number of nodes at any single depth) of \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}${\mathcal T}$\end{document} . These bounds are optimal up to the constant in the exponent when c satisfies \documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}$\sum_{i=1}^n c_i^2=O(n)$\end{document} ; the latter can be viewed as a “finite variance” condition for the child sequence. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012