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