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

DOI10.1002/rsa.20210zbMath1147.60316MaRDI QIDQ3522830

Nikolaos Fountoulakis, Bruce A. Reed

Publication date: 4 September 2008

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20210

zbMATH Keywords

mixing time; random graph; giant component

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

60G50: Sums of independent random variables; random walks

Related Items

Lack of Hyperbolicity in Asymptotic Erdös–Renyi Sparse Random Graphs, Algebraic and combinatorial expansion in random simplicial complexes, Mean field conditions for coalescing random walks, Mixing time of near-critical random graphs, Hypercube percolation, Critical random graphs: Diameter and mixing time, Mixing times of random walks on dynamic configuration models, Random walks on the random graph, Simple random walk on long range percolation clusters. I: Heat kernel bounds, Mixing of the symmetric exclusion processes in terms of the corresponding single-particle random walk, Cutoff for random walk on dynamical Erdős-Rényi graph, Expansion in supercritical random subgraphs of the hypercube and its consequences, Random walk on sparse random digraphs, Fast mixing via polymers for random graphs with unbounded degree, The mixing time of the giant component of a random graph, Smoothed Analysis on Connected Graphs, Anatomy of a young giant component in the random graph, Stochastic forms of non-negative matrices and Perron-regularity

Cites Work

• Unnamed Item
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Faster mixing via average conductance