The Evolution of the Mixing Rate

Abstract

In this paper 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 (ln n lnln n)^{1/2}, proving that the mixing time in this case is O((ln 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 O(ln n/ln d). We proved these results during the 2003-04 academic year. Similar results but for constant d were later proved independently by I. Benjamini, G. Kozma and N. Wormald.

15 pages

Cited by in corpus (7)

• Critical random graphs: Diameter and mixing time
• Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters
• The Cover Time of Random Walks on Graphs
• Duality and evolving set bounds on mixing times
• Long Range Percolation Mixing Time
• Graph-Theoretic Analysis of Belief System Dynamics under Logic Constraints
• A note on percolation on Z^d: isoperimetric profile via exponential cluster repulsion