Europhys. Lett.
Volume 65, Number 2, January 2004
Page(s) 151 - 157
Section General
Published online 01 January 2004
Europhys. Lett., 65 (2) , pp. 151-157 (2004)
DOI: 10.1209/epl/i2003-10081-7

Leadership statistics in random structures

E. Ben-Naim1 and P. L. Krapivsky2

1  Theoretical Division and Center for Nonlinear Studies Los Alamos National Laboratory - Los Alamos, NM, 87545 USA
2  Center for Polymer Studies and Department of Physics Boston University - Boston, MA, 02215 USA

(Received 31 July 2003; accepted in final form 18 November 2003)

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.

02.50.-r - Probability theory, stochastic processes, and statistics.
05.40.-a - Fluctuation phenomena, random processes, noise, and Brownian motion.
89.75.Hc - Networks and genealogical trees.

© EDP Sciences 2004