Premium
Changes of leadership in a random graph process
Author(s) -
Erdös Paul,
Łuczak Tomasz
Publication year - 1994
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240050122
Subject(s) - random graph , combinatorics , graph , mathematics , random regular graph , discrete mathematics , line graph , pathwidth
Abstract Let 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 as n →∞, of the order of n /log log n /log n . © 1994 John Wiley & Sons, Inc.