Premium
The mixing time of the giant component of a random graph
Author(s) -
Benjamini Itai,
Kozma Gady,
Wormald Nicholas
Publication year - 2014
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.20539
Subject(s) - expander graph , mixing (physics) , random graph , random walk , mathematics , combinatorics , constant (computer programming) , vertex (graph theory) , component (thermodynamics) , exponential function , discrete mathematics , graph , statistical physics , computer science , physics , statistics , mathematical analysis , quantum mechanics , programming language
We show that the total variation mixing time of the simple random walk on the giant component of supercritical G ( n , p ) and G ( n , m ) is Θ ( log 2 n ) . This statement was proved, independently, by Fountoulakis and Reed. Our proof follows from a structure result for these graphs which is interesting in its own right. We show that these graphs are “decorated expanders” — an expander glued to graphs whose size has constant expectation and exponential tail, and such that each vertex in the expander is glued to no more than a constant number of decorations. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 383–407, 2014