Parking Functions, Empirical Processes, and the Width of Rooted Labeled Trees

Abstract

This paper provides tight bounds for the moments of the width of rooted labeled trees with $n$ nodes, answering an open question of Odlyzko and Wilf (1987). To this aim, we use one of the many one-to-one correspondences between trees and parking functions, and also a precise coupling between parking functions and the empirical processes of mathematical statistics. Our result turns out to be a consequence of the strong convergence of empirical processes to the Brownian bridge (Komlós, Major and Tusnády, 1975).