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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom