The evolution of the mixing rate of a simple random walk on the giant component of a random graph

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 th...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2008-08, Vol.33 (1), p.68-86
Main Authors: Fountoulakis, N., Reed, B.A.
Format: Article
Language:English
Subjects:
giant component
mixing time
random graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.20210