tailieunhanh - Báo cáo toán học: "Parking functions, empirical processes, and the width of rooted labeled trees"

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Parking functions, empirical processes, and the width of rooted labeled trees. | Parking functions empirical processes and the width of rooted labeled trees Philippe Chassaing Institut Elie Cartan Vandoeuvre France chassain@ Jean-Franẹois Marckert Universite de Versailles St-Quentin en Yvelines Versailles France marckert@ Submitted August 31 1999 Accepted February 8 2001. MR Subject Classifications 05C05 60J65 60J80 62G30 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 Komlos Major and Tusnady 1975 . Key words. Rooted labeled trees moment width Brownian excursion empirical processes hashing with linear probing parking. 1 Introduction An order n 1 labeled tree is a connected graph with set of vertices 0 1 2 3 . ng and with n edges. If we specify one vertex to be the root we have a rooted labeled tree. According to Cayley 1889 the number of such trees is n 1 n. For T chosen at random in the set of order n 1 rooted labeled trees let G T denote the number of nodes at distance k from the root of T and let Hn T denote the maximum distance of a node from the root the height of T G jn k 0 is the profile of the tree. The width Wn T is defined by Wn max Gk . 0 k Hn THE ELECTRONIC JOURNAL OF COMBINATORICS 8 2001 R14 1 Odlyzko and Wilf 1987 used a Perron-Frobenius-like theory to derive asymptotics for the cumulative function of Wn. They also proved that Clin E Wn C2 Jnlogn and left the first term in the asymptotic of E Wn as an open question. Let t denote the local time of the normalized Brownian excursion e . at level t . 1 c1 _ t m í L I t t e u 0- J 0 1 du. Aldous 1 conjectured that t I Gụp ịh n .