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

Fix a sequence c = (c₁,…,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₁,…,v_n so that for each 1 ≤ i ≤ n, v_i has exactly c_i children. Let <span>\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}${\mathcal T}$\end{document} **image**</span> 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 <span>\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}${\mathcal T}$\end{document} **image**</span>. These bounds are optimal up to the constant in the exponent when c satisfies <span>\documentclass{article}\usepackage{mathrsfs}\usepackage{amsmath}\pagestyle{empty}\begin{document}$\sum_{i=1}^n c_i^2=O(n)$\end{document} **image**</span>; the latter can be viewed as a “finite variance” condition for the child sequence. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012 © 2012 Wiley Periodicals, Inc.