\documentclass[twocolumn,showpacs,aps]{revtex4}
%\documentclass[preprint,showpacs]{revtex4}
\usepackage{epsf}
\begin{document}
\title{Leadership Statistics in Random Structures}
\author{E.~Ben-Naim}
\email{ebn@lanl.gov} \affiliation{Theoretical Division and Center
for Nonlinear Studies, Los Alamos National Laboratory,  Los
Alamos, New Mexico, 87545 USA}
\author{P.~L.~Krapivsky}
\email{paulk@bu.edu} \affiliation{Center for Polymer Studies and
Department of Physics, Boston University, Boston, MA, 02215 USA}
\begin{abstract}
The largest component (``the leader'') in evolving random structures
often exhibits universal statistical properties. This phenomenon is
demonstrated analytically for two ubiquitous structures: random trees
and random graphs. In both cases, lead changes are rare as the average
number of lead changes increases quadratically with logarithm of the
system size. As a function of time, the number of lead changes is
self-similar. Additionally, the probability that no lead change ever
occurs decays exponentially with the average number of lead changes.
\end{abstract}
\pacs{02.50.-r, 05.40.-a, 89.75Hc}
\maketitle 

Extreme statistics are important in science, engineering, and society
as they dictate catastrophic events, systems robustness, financial
indices, etc. The theory of extreme statistics provides a powerful
analysis framework and prediction tool \cite{res,jg}. However, it is
limited to ensembles of {\em independent} random variables.  Even
though most practical applications involve correlated random
variables, such cases remain largely unexplored \cite{bm,bkm,mk}.

We investigate extremal characteristics of two basic random
structures: random trees and random graphs. Random trees appear in
data storage algorithms in computer science \cite{hmm,dek,ws} and in
physical processes such as collisions in gases \cite{vvd}.  Random
graphs \cite{bb,jlr} have numerous applications to theoretical
computer science \cite{dek,ws}, social networks \cite{sp,gn}, and
physical processes such as polymerization \cite{pjf}.

We focus on the largest component, the leader, and ask: What is the
size of the leader?  How does the number of lead changes depend on
time and system size?  What is the probability that the leader never
changes? Similar questions were investigated in growing networks
\cite{mda,kr}, and related leadership statistics were studied in
random graphs by Erd\H os and \L uczak \cite{tl}.

Random trees and random graphs are special cases of aggregation
processes and hence, we analyze them using the rate equation approach
\cite{mvs,sc,jbm,hez}.  Characterization of leadership statistics is
sensible only for finite systems.  We thus consider large yet finite
systems for which the rate equation approach yields the leading
asymptotic dependence on the system size \cite{aal,jls,ve,aldous}.

Our main result is that the total number of lead changes $L$ grows as
$L(N)\sim[\ln N]^2$ with the system size $N$. This as well as other
leadership statistics are universal as they characterize both random
trees and random graphs.  The time dependent number of lead changes
$L(t,N)$ attains the scaling form $(\ln N)^2\,F(x)$ with the scaling
variable $x=\ln k_*/\ln N$ where $k_*$ is the typical component size
at time $t$. Additionally, the probability that no lead change has ever
occurred decays as $e^{-L}$.

We start with the simpler case of random trees.  A tree is a
hierarchical structure of connected nodes. We term the top node the
root and the bottom nodes the leafs (see Fig.~1). Initially, the
system consists of $N$ trivial trees in which the root is also a
leaf. We grow an ensemble (a forest) of trees using a recursive
procedure in which two trees are picked at random and attached to a
common root (Fig.~1).  This merging process is repeated until a
single tree with $N$ leafs emerges.

We treat the merger process dynamically. Let $n$ be the number of
trees. The transition $n\to n-1$ occurs with rate $r_n$ proportional
to the total number of pairs. Choosing $2/N$ as the merger rate for
each pair (i.e., $r_n=n(n-1)/N$) is convenient as in the thermodynamic
limit $N\to\infty$, the normalized density $c=n/N$ evolves according
to $\frac{d}{dt}c=-c^2$.  Subject to the initial condition $c(0)=1$
the density is $c(t)=(1+t)^{-1}$.  We state the results in terms of
time $t$; the results can be easily reformulated in terms of the number of
trees $n=N(1+t)^{-1}$.

\begin{figure}[t]
\centerline{\epsfxsize=7.6cm\epsfbox{fig1.eps}} \caption{Illustration
of the tree merger process with system size $N=4$. Nodes are denoted
by circles, with the top node (the root) denoted by a bullet. The
bottom nodes are the leafs.}
\end{figure}

The size distribution is obtained similarly. Let $n_k$ be the number
of trees with $k$ leafs. The normalized density $c_k=n_k/N$ evolves
according to the Smoluchowsky rate equation
\hbox{$\frac{d}{dt}c_k=\sum_{i+j=k}c_ic_j-2cc_k$} with the
monodisperse initial conditions $c_k(0)=\delta_{k,1}$. The rate
equation reflects the fact that trees are merged randomly, independent
of their size. It can be solved (using the generating functions
technique for example) to give \cite{mvs,sc}
\begin{equation}
\label{ckt-sol}
c_k(t)=\frac{t^{k-1}}{(1+t)^{k+1}}.
\end{equation}
In the long time limit, the size distribution attains a simple
self-similar behavior
\begin{equation}
\label{ckt-scl}
c_k(t)\simeq k_*^{-2}\Phi(k/k_*),\qquad \Phi(x)=e^{-x}
\end{equation}
with the typical size $k_*\simeq t$.

{\it What is the average size of the largest tree (the leader)?} Using
the size distribution, we can answer an even more general
question. Let $l_r(t)$ be the average size of the $r$-largest tree
with the leader $l\equiv l_1$.  From the cumulative distribution
$u_k=\sum_{j\geq k} n_j=Nt^{-1}[t/(1+t)]^k$ and the relation
$u_{l_r}=r$, the size of the $r$th leader is
\begin{equation}
\label{lt-sol}
l_r(t,N)=\frac{\ln[N/rt]}{\ln[(1+t)/t]}\,.
\end{equation}

There are two regimes of behavior. In the short time limit, $t\ll 1$,
one has $l_r(t,N)=1+\ln[N/r]/\ln[1/t]$. Moreover, from $n_k\simeq
Nt^{k-1}$ the first dimer appears at $t_2\simeq N^{-1}$; the first
trimer appears at $t_3\simeq N^{-1/2}$ and then, there are of the
order $N^{1/2}$ dimers, so this trimer results from the leading dimer
with probability of the order $N^{-1/2}$.  At the crossover point,
$t\approx 1$, the size of the leader varies logarithmically with the
system size, \hbox{$l(t\approx 1,N)\sim \ln N$}. In the long time
limit, $t\gg 1$, the size of the leader grows linearly (up to a
logarithmic correction) with time
\begin{equation}
\label{lt-late}
l_r(t,N)\simeq t\, \ln\frac{N}{rt}\,.
\end{equation}

\begin{figure}[t]
\centerline{\epsfxsize=7.6cm\epsfbox{fig2.eps}} \caption{The
normalized time dependence of the number of lead changes for random
trees, $L(t,N)/L(N)$, versus the scaling variable $x=\ln t/\ln N$.
The simulation data, representing an average over $10^3$ Monte Carlo
runs, is compared with the theoretical prediction $2F(x)=2x-x^2$.}
\end{figure}

{\it What is the average size $l_w$ of the winner (the leader that
  never relinquishes the lead)?  At what time $t_w$ does the winner
  emerge?}  Both quantities grow linearly with $N$: $l_w\simeq\alpha
  N$ and $t_w\simeq\beta N$ as follows from Eq.~(\ref{lt-late}). The
  curve $\alpha=-\beta\ln \beta$ has an extremum at
  $\alpha=\beta=e^{-1}\cong0.36788$ thereby implying the bounds:
  $\alpha,\beta<e^{-1}$. Finding the values of $\alpha$ and $\beta$ is
  an open problem.

{\it How many lead changes $L(t,N)$ occur as a function of time? As a
function of system size? What is the total number of lead changes
$L(N)\equiv L(t=\infty,N)$?}  In our definition, a lead change occurs
when two trees (none of which is the leader) merge to become larger
than the leader. For short times, $t\ll 1$, almost every lead change
introduces a new leader, and since the leader grows in increments of
unity $L(t,N)=l(t,N)-1$. For long times, $t\gg 1$, consider the
cumulative distribution $u_k\simeq Nt^{-1}\exp(-k/t)$.  Its growth
rate immediately gives the rate by which the leader is surpassed,
$\frac{d}{dt}L(t,N)=\frac{d}{dt}u_k\big|_{k=l}$ (this rate properly
accounts for events in which two non-leaders are merging to surpass the
leader). As $u_l\simeq 1$, we have $\frac{d}{dt}L(t,N)\simeq
lt^{-2}\simeq t^{-1}\ln \frac{N}{t}$ from which the time-dependent
number of lead changes is
\begin{equation}
\label{ltn-sol}
L(t,N)\simeq\ln t\ln N-\frac{1}{2}(\ln t)^2.
\end{equation}
Interestingly, this quantity obeys the scaling form
\begin{equation}
\label{ltn-scl}
L(t,N)=(\ln N)^2\,F(x), \qquad x=\frac{\ln t}{\ln N}
\end{equation}
with the quadratic scaling function: $F(x)=x-\frac{1}{2}x^2$ (Fig.~2).
The scaling variable is unusual: a ratio of logarithms, in contrast
with the ordinary ratio underlying the size distribution
(\ref{ckt-scl}).

To check these theoretical predictions, we performed large-scale Monte
Carlo simulations.  In the simulations, randomly chosen trees are
merged repeatedly. Keeping track of the leader and averaging over many
independent realizations, we observe a scaling behavior that is
consistent with Eq.~(\ref{ltn-scl}). However, as a function of the
system size, the convergence is slow because the scaling variable
involves logarithms.

\begin{figure}[t]
\centerline{\epsfxsize=7.6cm\epsfbox{fig3.eps}} \caption{The total
    number of lead changes $L(N)$ versus the system size $N$.  Shown
    are simulation results for Random Trees (RT) and Random Graphs
    (RG) representing an average over $10^4$ realizations. }
\end{figure}

The time dependent behavior can be used to obtain the total number of
lead changes. Substituting $t_w=\beta N$ into Eq.~(\ref{ltn-sol})
gives
\begin{equation}
\label{ln}
L(N)\simeq A(\ln N)^2\,
\end{equation}
with $A=F(1)=1/2$. Both the leading asymptotic behavior and the $\ln
N$ correction are confirmed numerically. Moreover, the numerical
prefactor $A=0.50(1)$ agrees with the theoretical prediction
(Fig.~3). Since $L(t\approx 1,N)\sim \ln N$, the majority of lead
changes occur when $t\gg 1$.

{\it How is the number of lead changes distributed?} {\it What is the
  probability that no lead change occur?} Let $P_n(t,N)$ be the
  probability that $n$ lead changes occur till time $t$. We assume
  that the flux surpassing the leader characterizes the evolution of
  the probability distribution
  \hbox{$\frac{d}{dt}P_n=(\frac{d}{dt}L)\,[P_{n-1}-P_n]$}.  With the
  initial condition $P_n(0,N)=\delta_{n,0}$, the distribution is
  Poissonian
\begin{equation}
\label{pn}
P_n(t,N)=\frac{[L(t,N)]^n}{n!}\,e^{-L(t,N)}.
\end{equation}
Consequently, the distribution of the total number of lead changes
\hbox{$P_n(N)\equiv P_n(t=\infty,N)$} is also Poissonian:
\hbox{$P_n(N)=\frac{L^n}{n!}\,e^{-L}$} with $L\equiv L(N)$ given by
(\ref{ln}).  Hence, the standard deviation in the number of lead changes
$\sigma(N)$ grows as $\sigma(N)\simeq \sqrt{A}\ln N$.  Furthermore,
the probability that no lead change occur (the survival probability
of the first leader) $S(N)\equiv P_0(N)$ decays faster than a
power-law but slower than a stretched exponential
\begin{equation}
\label{sn}
S(N)=\exp[-L]\simeq \exp\left[-A(\ln N)^2\right].
\end{equation}
The asymptotic $N$-dependence is confirmed numerically (Fig.~4).

\begin{figure}[t]
\centerline{\epsfxsize=7.6cm\epsfbox{fig4.eps}} \caption{The survival
probability of the initial leader $S(N)$ versus the system size
$N$. The number of realizations was $10^{10}$ and $10^8$ for random
trees and random graphs, respectively.}
\label{sn-fig}
\end{figure}

We now consider graphs, grown randomly as follows.  Initially, the
system consists of $N$ single-node graphs.  Then, two nodes are picked
at random and a link is drawn between them. If they belong to two
distinct graphs, the two become one. This process is repeated
indefinitely.  Let $n_k$ be the number of graphs of size $k$.  The
normalized density $c_k=n_k/N$ evolves according to the rate equation
$\frac{d}{dt}c_k=\frac{1}{2}\sum_{i+j=k}ijc_ic_j-k\,c_k$ with the
monodisperse initial conditions $c_k(0)=\delta_{k,1}$. The rate
equation reflects the fact that two graphs are connected with rate
proportional to the product of their sizes.  This equation can be
solved using generating functions to give \cite{jbm,hez}
\begin{equation}
\label{rg-ckt-sol}
c_k(t)=\frac{(kt)^{k-1}}{k\cdot k!}e^{-kt}.
\end{equation}

At time $t=1$, the system undergoes a gelation transition: it develops a
giant component that eventually takes over the entire system.  Close to the
gelation time, the size distributions attains the scaling behavior
\begin{equation}
\label{rg-ckt-scl}
c_k(t)\simeq k_*^{-5/2}\Phi(k/k_*),\qquad \Phi(x)\propto x^{-5/2}e^{-x/2}.
\end{equation}
The typical size diverges: \hbox{$k_*\simeq (1-t)^{-2}$} as $t\to
1$. At the gelation time, the size distribution develops an algebraic
tail \hbox{$c_k(t=1)\sim k^{-5/2}$}.  Hence, the cumulative
distribution is \hbox{$u_k\sim Nk^{-3/2}$} and with the criterion
$u_{l_w}\sim 1$ we obtain the average size of the giant component (the
winner): $l_w\sim N^{2/3}$ \cite{bb}.  The time at which it emerges is
$1-t_w\sim N^{-1/3}$.

The size of the leader is again estimated from the relation $u_l=1$.  For
$t\ll 1$, the size of the leader $l(t,N)$, the number of lead changes
$L(t,N)$, as well as the number of distinct leaders are all approximately
equal and the same as for random trees.  The number of lead changes is of the
order $\ln N$ in this phase; furthermore, $L(t,N)\sim \ln N$ for $t<1$. The
behavior near the gelation time $1-t\ll 1$ is a bit more interesting. {}From
the large-$k$ behavior, \hbox{$u_k\sim
  N(1-t)^{-2}k^{-5/2}\exp[-k(1-t)^2/2]$}, and $u_l=1$ we arrive at following
implicit relation for the leader $l(t,N)$: \hbox{$l\simeq 2(1-t)^{-2}\,\ln
  N-3(1-t)^{-2}\,\ln l\,$}.  Inserting the zeroth order approximation
\hbox{$l^{(0)}=2(1-t)^{-2}\,\ln N$} into $\ln l$ on the right-hand side of
the above relation and ignoring $\ln\ln N$ terms yields the leader size
\begin{equation}
\label{rg-lt-late}
l\simeq\frac{2}{(1-t)^2}\,\ln [N(1-t)^3].
\end{equation}
The rate by which the leader changes is estimated from
$\frac{d}{dt}L=\frac{d}{dt}u_k\big|_{k=l}\simeq
l(1-t)$. Substituting Eq.~(\ref{rg-lt-late}) and integrating, the
number of lead changes is
\begin{equation}
\label{rg-lnt}
L(t,N)\simeq 2\,\ln N\,\ln\frac{1}{1-t}
-3\left[\ln \frac{1}{1-t}\right]^2\,.
\end{equation}
It attains the scaling form
\begin{equation}
\label{rg-ltn-scl}
L(t,N)\simeq (\ln N)^2\,F(x), \qquad
x=\frac{\ln\frac{1}{1-t}}{\ln N}
\end{equation}
with the scaling function $F(x)=2x-3x^2$.  As this behavior holds up
to time $t_w$, where $1-t_w\sim N^{-1/3}$, the total number of lead
changes grows according to Eq.~(\ref{ln}) with
$A=F(1/3)=1/3$. Furthermore, the distribution of lead changes is
Poissonian as in (\ref{pn}) and the survival probability decays
according to (\ref{sn}).

As terms of the order $\ln\ln N/\ln N$ were neglected, the scaling
behavior and the leading asymptotic behavior may be realized only for
extremely large systems. Moreover, the computational cost of random
graph simulations is larger because graphs are chosen with probability
proportional to their size. Nevertheless, we can confirm the predicted
system size dependence of $L(N)$ (Fig.~2) and $S(N)$ (Fig.~3)
numerically. The prefactor $A=0.20(2)$ is lower than the theoretical
value $A=1/3$, perhaps due to the slow convergence.

Let us compare random trees and random graphs. They seem very
different, e.g., the gelation transition occurs in one case but not in
the other. Yet, they exhibit similar extremal characteristics.  In
both cases, the total number of lead changes $L(N)$ grows as $[\ln
N]^2$ and the survival probability decays as $\exp[-L]$.  Moreover,
even the seemingly distinct temporal characteristics can be
reconciled, e.g., in both cases the size distribution attains the
scaling form $c_k(t)\propto \Phi(k/k_*)$ when $t\to\infty$ (for random
trees) and $t\to 1$ (for random graphs). Of course, the actual time
dependence of the typical scale is different: $k_*\sim t$ and $k_*\sim
(1-t)^{-2}$, respectively. The size of the leader can be rewritten as
$l\approx k_*\ln [N/k_*^\gamma]$ with $\gamma=1$ and $3/2$,
respectively.  Furthermore, Eqs.~(\ref{ltn-scl}) and
(\ref{rg-ltn-scl}) can be reconciled by writing the scaling variable
in the unified form $x=\ln k_*/\ln N$.

We now restrict our attention to the survival probability $S(N)$ and
supplement the leading behavior (\ref{sn}) with bounds.  Consider
random trees. A lower bound for $S(N)$ is obtained from a greedy
scenario in which all merger events involve the leader till it reaches
size $N/2$. The probability that the second merger involves the
leading dimer is $(N-1)^{-1}$; the probability that the third merger
involves the leading trimer is $(N-2)^{-1}$; etc.  Thus, the greedy
scenario is realized with probability $\prod_{j<N/2}\frac{1}{N-j}$,
thereby providing the lower bound $S(N)>\frac{(N/2)!}{(N-1)!}$.  An
upper bound can be obtained by estimating the number of trees the size
of the leader. There are of the order $N^{1/2}$ dimers when the first
trimer is born, $n_2(t_3=N^{-1/2})=N^{1/2}$. The leading dimer retains
the lead with probability inversely proportional to the number of
dimers, $N^{-1/2}$. Similarly, this leading trimer retains the lead
with probability proportional to $N^{-1/3}$. Therefore the upper bound
$\prod_{j<\ln N} N^{-1/j}$ is estimated as $N^{-\ln \ln N}$ (the
cutoff $j<\ln N$ is dictated by the size of the leader at the
crossover time $t\approx 1$).  Hence, the survival probability obeys
\begin{equation}
\label{bounds-rt} \left(\frac{e}{2N}\right)^{\frac{N}{2}}<S(N) <
\exp\left[-(\ln N)\cdot(\ln\ln N)\right],
\end{equation}
where the lower bound was simplified using the Stirling formula.  Note
that the upper bound merely assures that the lead never changes in the
early phase $t<1$ when the average number of lead changes is only $\ln
N$.

For random graphs, the greedy scenario is again simple to analyze
since the probability that in a system with a leader of size $j$ and
$N-j$ monomers the probability that the next merger involves the
leader is \hbox{$p_j=[j(N-j)]/[j(N-j)+\frac{1}{2}\,(N-j)(N-j-1)]$} or
$p_j=(2j)/(N+j-1)$. The product $\prod_{j<N/2}p_j$ provides the lower
bound.  Asymptotically, the lower bound decays as $\lambda^N$ with
$\lambda=(2/3)^{3/2}=0.544331\ldots$. On the other hand, repeating the
above argument yields the same upper bound, so
\begin{equation}
\label{bounds-rg}
\lambda^N<S(N)<\exp\left[-(\ln N)\cdot(\ln\ln N)\right]\,.
\end{equation}
The upper bound is again much closer to the actual asymptotic behavior.

In conclusion, random graphs and random trees exhibit similar
leadership characteristics. As in random growing networks \cite{kr},
lead changes are infrequent given that the overall number of lead
changes increases only logarithmically with the system size.  The time
dependent number of lead changes approaches a self-similar form
asymptotically. The convergence to the asymptotic behavior is much
slower for extremal statistics compared with size statistics due to
the various logarithmic dependences.  Consequently, the asymptotic
behavior may difficult to detect in practice, especially for random
graphs.

To obtain the extremal characteristics, we employed the scaling
behavior of the size distribution outside the scaling regime, namely,
at sizes much larger than the typical size where, at least formally,
statistical fluctuations can no longer be ignored.  Interestingly, the
resulting system size dependence for the various leadership statistics
appears to be asymptotically exact. Further analysis is needed to
illuminate the role of statistical fluctuations, for example by
characterizing corrections to the leading behavior.

The virtue of the rate equation approach to analyzing extremal
characteristics is its simplicity, robustness, and generality. It
applies to general aggregation processes where the merger rate may
depend in a complicated manner on the aggregate size or in situations
where there is an underlying spatial structure. We find that the above
leadership statistics extend to algebraic merger rates as well as to
aggregation in one spatial dimension \cite{bk}. This method is also applicable
to other extremal features including for example laggard (smallest
component) statistics. In the case of random trees, for instance, the
total number of laggard changes grows logarithmically with the system
size.

\acknowledgments 
We are thankful to Sidney Redner for many discussions and initial
collaboration on this work. This research was supported in part by
DOE(W-7405-ENG-36).

\begin{thebibliography}{99}

\bibitem{res}
   R.~E.~Ellis, {\em Entropy, Large Deviations, and Statistical Mechanics}
   (Springer-Verlag, New York, 1985).

\bibitem{jg}
   J.~Galambos, {\em The Asymptotic Theory of Extreme Order Statistics}
   (R.E. Krieger Publishing Co., Malabar, 1987).

\bibitem{bm}
   J.-P.~Bouchaud and M.~Mezard,
   J. Phys.\ A {\bf 30}, 7997 (1997).

\bibitem{bkm}
   E.~Ben-Naim, P.~L.~Krapivsky, and S.~N.~Majumdar,
   Phys.\ Rev.\ E {\bf 64}, 035101(R) (2001).

\bibitem{mk}
   S.~N.~Majumdar and P.~L.~Krapivsky, Physica A {\bf 318}, 161 (2003).

\bibitem{hmm}
   H.~M.~Mahmoud,
   {\em Evolution of Random Search Trees}
   (John Wiley \& Sons, New York, 1992).

\bibitem{dek}
   D.~E.~Knuth,
   {\em The Art of Computer Programming, vol. 3, Sorting and Searching}
   (Addison-Wesley, Reading, 1998).

\bibitem{ws}
   W.~Szpankowski,
   {\em Average Case Analysis of Algorithms on Sequences}
   (John Wiley \& Sons, New York, 2001).

\bibitem{vvd}
   R. van Zon, H. van Beijeren, and Ch. Dellago,
   Phys. Rev. Lett. {\bf 80}, 2035 (1998).

\bibitem{bb}
   B.~Bollob\'as,
   {\em Random Graphs} (Academic Press, London, 1985).

\bibitem{jlr}
   S.~Janson, T.~\L uczak, and A.~Rucinski,
   {\em Random Graphs} (John Wiley \& Sons, New York, 2000).

\bibitem{sp}
   B.~Skyrms and R.~Pemantle,
   Proc.\ Natl.\ Acad.\ Sci.  {\bf 97}, 9340 (2000).

\bibitem{gn}
   M.~Girvan and M.~E.~J.~Newman,
   Proc.\ Natl.\ Acad.\ Sci. {\bf 99}, 7821 (2002).

\bibitem{pjf}
   P.~J.~Flory,
   {\em Principles of Polymer Chemistry} (Cornell, Ithaca, 1953).

\bibitem{mda}
   A.~A.~Moreira, J.~S.~de~Andrade Jr., and L.~A.~N.~Amaral,
   Phys.\ Rev.\ Lett. {\bf 89}, 268703 (2002).

\bibitem {kr}
   P.~L.~Krapivsky and S.~Redner,
   Phys.\ Rev.\ Lett. {\bf 89}, 258703 (2002).

\bibitem{tl}
   T.~\L uczak, Random Struct.\ Algorithms {\bf 1}, 287 (1990);
   P.~Erd\H os and T.~\L uczak, Random Struct.\ Algorithms
     {\bf 5}, 243 (1994).

\bibitem{mvs}
   M.~V.~Smoluchowski,
   Z. Phys.\ Chem. {\bf 92}, 215 (1917).

\bibitem{sc}
   S.~Chandrasekhar, Rev.\ Mod.\ Phys. {\bf 15}, 1 (1943).

\bibitem{jbm}
   J.~B.~McLeod,
   Quart.\ J. Math.\ Oxford {\bf 13}, 119 (1962); 
   {\it ibid} {\bf 13}, 193 (1962); 
   {\it ibid} {\bf 13}, 283 (1962).  

\bibitem{hez}
   E.~M.~Hendriks, M.~H.~Ernst, and R.~M.~Ziff,
   J. Stat.\ Phys. {\bf 31}, 519 (1983).

\bibitem{aal}
   A.~A.~Lushnikov, J. Colloid\ Inter.\ Sci. {\bf 65}, 276 (1977).

\bibitem{jls}
   J.~L.~Spouge, J. Colloid Inter.\ Sci. {\bf 107}, 38 (1985).

\bibitem{ve}
   P.~G.~J van Dongen and M.~H.~Ernst, 
   J. Stat.\ Phys. {\bf 49}, 879 (1987).

\bibitem{aldous}
   D.~J.~Aldous, Bernoulli {\bf 5}, 3 (1999). 

\bibitem{bk}
   E.~Ben-Naim and P.~L.~Krapivsky, unpublished.

\end{thebibliography}
\end{document}



