Premium
The evolution of the mixing rate of a simple random walk on the giant component of a random graph
Author(s) -
Fountoulakis N.,
Reed B.A.
Publication year - 2008
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.20210
Subject(s) - random walk , giant component , mixing (physics) , mathematics , component (thermodynamics) , combinatorics , random graph , degree (music) , simple random sample , statistical physics , graph , discrete mathematics , statistics , physics , thermodynamics , quantum mechanics , population , demography , sociology , acoustics
Abstract In this article we present a study of the mixing time of a random walk on the largest component of a supercritical random graph, also known as the giant component. We identify local obstructions that slow down the random walk, when the average degree d is at most O ( $ \sqrt{\ln n} $ ), proving that the mixing time in this case is Θ(( n / d ) 2 ) asymptotically almost surely. As the average degree grows these become negligible and it is the diameter of the largest component that takes over, yielding mixing time Θ( n / d ) a.a.s.. We proved these results during the 2003–04 academic year. Similar results but for constant d were later proved independently by Benjamini et al. in 3. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008