##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 792.60009

**Autor: ** Erdös, Paul; Luczak, Tomasz

**Title: ** Changes of leadership in a random graph process. (In English)

**Source: ** Random Struct. Algorithms 5, No.1, 243-252 (1994).

**Review: ** Let **{**G(n,M)**}**^{\binom}{n}{2}_{M = 0} be a random graph process in which in each step we add to a graph a new edge, chosen at random from all available pairs. Define the leader of G(n,M) as either the unique largest component or, if G(n,M) contains many components of the maximum size, the one from the largest components which emerged first during the process. We show that the longest period between two changes of leaders in the random graph process is, with probability tending to 1 and n ––> oo, of the order of n log log n/ log n.

**Classif.: ** * 60C05 Combinatorial probability

05C80 Random graphs

**Keywords: ** random graph process

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag