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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page