On the Width of Labeled Trees
JeanFrançois Marckert
Université de Nancy 1
Algorithms Seminar
April 12, 1999
[summary by Christine Fricker]
A properly typeset version of this document is available in
postscript and in
pdf.
If some fonts do not look right on your screen, this might be
fixed by configuring your browser (see the documentation here).
Abstract
We consider A_{n} the set of all rooted labeled trees with n
nodes. We denote by Z_{i} the number of nodes at distance i from
the root and by W_{n}=max_{0£ i £ n} Z_{i} the width of the
tree. The aim of the talk is to present results on convergence of moments of
W_{n} (correctly renormalized) to those of the maximum of the
normalized Brownian excursion and to give a
tight bound for the rate of convergence.
For the
proof, the
connections between especially breadth first search random walk on trees, random walk with Poissonian
increment, parking function and empiric process of
mathematical statistics are described.
The results presented in this talk were obtained jointly with
P. Chassaing.
1 Introduction
A rooted labeled tree with n nodes is a connected graph with n
vertices and n1 edges where a vertex, the
root, is specified. Tight bounds of the width W_{n} of rooted labeled trees
with n nodes are given, answering an open question of Odlyzko and Wilf
[3] that E(W_{n}) is
between C_{1}(n)^{1/2} and C_{2}(nlogn)^{1/2}.
More precisely, we first present the result of Takacs [6]
that W_{n}/(n)^{1/2} converges in distribution to the maximum m of
the Brownian excursion, with the wellknown theta distribution given by
Pr 
(m£ x)=


(14k^{2}x^{2})e 

.

However weak convergence does not answer completely the question of
Odlyzko and Wilf. To fill this gap, we prove that
Theorem 1
For all p³
1, E(W_{n}^{p}/n^{p/2})E(m^{p})£ C_{p} n^{1/4}(logn)^{1/2} where
m is the maximum of the normalized Brownian excursion.
The moments
of m are wellknown and given by
E(m^{p})=p(p1)G(p/2)z(p)2^{p/2}.
For this we prove that there exists a sequence of normalized Brownian excursions
of maximum m_{n} such that,
for all p³
1,
E( 
 
W_{n}/(n)^{1/2}m_{n} 
 

)£ C'_{p} n^{p/4}(logn)^{1/2}

using that if q is defined by 1/p+1/q=1 and if X and Y are two real
random variables in L_{p}, then by Holder's inequality,
 
E(X^{p})E(Y^{p}) 
 
£ p

\ 
XY 
\ 

\ 
X+Y 
\ 

.

2 Relation Between Rooted Labeled Trees and Parking Functions
In hashing with linear probing or parking, we consider n cars
c_{i} (1£ i£ n) arriving in this order at random in n+1
places {0,1,...,n}, where car c_{i} is parking on its place h_{i}
if h_{i} is still empty, otherwise car c_{i} is trying places h_{i+1}
mod n+1,... . We consider parking functions, i.e. sequences
(h_{i})_{1£ i£ n} such that place n is empty. A parking
function is alternatively characterized by the sequence (A_{k}={i,h_{i}=k})
_{0£ k£ n} of sets of cars that arrive on place k, with
x_{k}=card A_{k}. If y_{k} is the number of cars that tried once to park on
place k,
y_{k}=y_{k1}1+x_{k}, y_{0}=x_{0}.
The fact that place n is the empty place is given by
y_{k}³ 1 (0£ k£ n1), y_{n}=0
or equivalently


x_{i}k³ 1 (0£ k£ n1), 

x_{i}n=0.
(1) 
A labeled tree with vertices {0,1,...,n} rooted at 0 is
also characterized by the sequence of disjoint sets (A_{k})_{0£ k£ n}
whose union is {1,...,n} and the x_{k}=card A_{k} satisfying (1). Indeed, A_{k} (k³ 1) (respectively
A_{0}) is defined as the set of new neighbors
of the smallest element in A_{k1} (respectively 0) and (1) is the condition for the tree to be connected
and to have root 0.
The number of A_{k} (k³ 1) with cardinality x_{k} (k³ 1)
is proportional to the product of Poisson probabilities
e^{1}/x_{k}!. In other words the corresponding unlabeled tree is a
GaltonWatson tree with Poisson(1) progeny, constrained to have n+1
nodes. Thus, the sequence y=(y_{k})_{0£ k£ n} is the discrete
excursion with length n of a random walk with increments
x_{k}1. It is wellknown that
(y_{ë ntû}/(n)^{1/2})_{0£ t£ 1} converges in
distribution to (e(t))_{0£ t£ 1} where e is a normalized
Brownian excursion and max_{k} y_{k}/(n)^{1/2} converges in
distribution to m=max_{0£ t£ 1} e(t), which is
thetadistributed.
The random walk
(y_{k}) (introduced in [1] and [5]) gives the profile
of the tree (Z_{k}) as a subsequence of (y_{k})
Z_{k+1}=y_{l(k)}
where l(k)=å_{i=1}^{k} Z_{i} and the width W_{n} as
We prove in the following proposition that W_{n}=max_{k} y_{l(k)} has the same
behavior as max_{k} y_{k}.
Proposition 1
For each p³ 1,
W_{n} 

y_{k} _{p}=O(n^{1/4}(log n)^{3/4}). 
This result is based on the slow variation of the sequence y=(y_{k})_{0£
k£ n}. Indeed, W_{c}(n) defined as the set of sequences
y=(y_{k})_{0£ k£ n} such that, for all k and m such that k+m£ n,
y_{m+k}y_{m}£ c(klog n)^{1/2}
satisfies the following lemma.
Lemma 1
For all a>0, there exists c>0 such that, for all n,
This can be proved using (see Petrov [4]) that, if (Y_{k}) is a random walk with
increments X_{k} satisfying E(X_{k})=0 and for some a>0,
E(exp(aX_{k})<¥, then there exists T,C_{1},C_{2}>0 such that
Pr(Y_{k}³ x)£ 
ì ï ï í ï ï î 

if 0£ x £ C_{1}T, 

if x ³ C_{1}T.



Then it remains to prove that E((max_{k} y_{k}/(n)^{1/2})^{p})®
E(m^{p}) and to estimate the rate of convergence.
This is the object of the next section.
3 Parking Functions and Empiric Processes
Consider the sequence (U_{i})_{1£ i£ n} of n i.i.d. random
variables uniformly distributed on [0,1]. Let F_{n}(t) be the
empiric distribution for (U_{i})_{1£ i£ n} i.e.
F_{n}(t)= 
card{iÎ {1,...,n},U_{i}£ t} 

n 

, (0£
t£ 1). 
Process (F_{n}(t)) converges to (F(t))=(t), the distribution function of the
uniform distribution. Especially, the empiric process (a_{n}(t))=((n)^{1/2}(
F_{n}(t)F(t)))_{0£ t£ 1} converges in distribution to the
Brownian bridge (b(t))_{0£ t£ 1}.
There is a precise connection between parking functions and empiric
processes. Indeed, consider the sequence (U_{i})_{1£ i£ n} of i.i.d. random
variables uniformly distributed on [0,1] and realize parking in
the following way: If
U_{i}Î[k1/n+1,k/n+1[, then car c_{i}
tries to park first on place h_{i}=k. The last empty place V is given
in terms of the empiric process.
Proposition 2
There is a unique T(n) in {0,1,...,n} such that
Moreover, T(n)=V.
It is easy to deduce that

½ ½ ½ ½ 

( 

a_{n}(t)


a_{n}(t)) 
½ ½ ½ ½ 
£ 

where e_{n}=(n)^{1/2} sup_{0£ t£
1}a_{n}(ë(n+1)tû/n+1)a_{n}(t) satisfies
the following proposition.
Proposition 3
There exists A, C and K such that for all x and n,
Pr(e_{n}³ Clog n +x)£ An^{1KC}e^{Kx}.
(2)
Then a_{n}(t) is replaced by a Brownian bridge b_{n}(t) using the
following result of Komlos, Major and Tusnady [2].
Theorem 2
There exists a sequence of Brownian bridges (b_{n})_{n³ 1} and A,
M, µ>0 such that for all n and x
where C_{n}=sup_{0£ t£ 1}c_{n}(t) verifies for all x
Pr(C_{n}³ Alog 
n +x)£ Me 

.
(3) 
Then

½ ½ ½ ½ 

( 

b_{n}(t)


b_{n}(t)) 
½ ½ ½ ½ 
£ 
1+2(e_{n}+C_{n}) 

(n)^{1/2} 

where C_{n} is introduced in Theorem 2. Using the fact that, if T is
the almost surely unique point
such that b(T)=min_{0£ t£ 1}b(t), then e=(e(t))_{0£
t£ 1}, defined by e(t)=b((T+t) mod 1)b(T), is a normalized
Brownian excursion independent of T, one has

½ ½ ½ ½ 

 

e_{n}(t) 
½ ½ ½ ½ 
£ 
1+2(e_{n}+C_{n}) 

(n)^{1/2} 

.
(4) 
Relations (2) and (3) give that
 e_{n}+C_{n} _{p} is bounded by K_{p}log n
and thus (4) gives the following result.
Theorem 3
For each p³ 1,

½½ ½½ ½½ ½½ 
m_{n} 

½½ ½½ ½½ ½½ 

=O( 

).

It is then easy to deduce Theorem 1.
References
 [1]

Aldous (David). 
Brownian excursions, critical random graphs and the multiplicative
coalescent. The Annals of Probability, vol. 25, n°2,
1997, pp. 812854.
 [2]

Komlós (J.), Major (P.), and Tusnády (G.). 
An approximation of partial sums of independent RV's, and the
sample DF. II. Zeitschrift für Wahrscheinlichkeitstheorie
und Verwandte Gebiete, vol. 34, n°1, 1976, pp. 3358.
 [3]

Odlyzko (Andrew M.) and Wilf (Herbert S.). 
Bandwidths and profiles of trees. Journal of Combinatorial
Theory. Series B, vol. 42, n°3, 1987, pp. 348370.
 [4]

Petrov (V. V.). 
Sums of independent random variables. 
SpringerVerlag, New YorkHeidelberg, 1975, x+346p.
Translated from the Russian by A. A. Brown, Ergebnisse der Mathematik und
ihrer Grenzgebiete, Band 82.
 [5]

Spencer (Joel). 
Enumerating graphs and Brownian motion. Communications on Pure
and Applied Mathematics, vol. 50, n°3, 1997,
pp. 291294.
 [6]

Takács (Lajos). 
Limit distributions for queues and random rooted trees. Journal
of Applied Mathematics and Stochastic Analysis, vol. 6, n°3,
1993, pp. 189216.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.