Critical random graphs: Diameter and mixing time

DOI10.1214/07-AOP358MaRDI QIDQ941296zbMATH OpenOpenAlexFDO

Authors Asaf Nachmias, Yuval Peres

Publication date 4 September 2008

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0701316

zbMATH Keywords

Connected componentMixing timePercolationRandom graphRandom walk

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Percolation (82B43)

Abstract: Let $mathcal{C}_1$ denote the largest connected component of the critical ErdH{o}s--R'{e}nyi random graph $G(n,frac1n)$. We show that, typically, the diameter of $mathcal{C}_1$ is of order $n^{1/3}$ and the mixing time of the lazy simple random walk on $mathcal{C}_1$ is of order $n$. The latter answers a question of Benjamini, Kozma and Wormald. These results extend to clusters of size $n^{2/3}$ of $p$-bond percolation on any $d$-regular $n$-vertex graph where such clusters exist, provided that $p(d-1)le1+O(n^{-1/3})$.

Review text

The mixing time of a random walk on a graph is defined as the waiting time \(t\) for closeness between the t-step transition probabilities and the stationary probabilities. For a random graph \(G(n,p)\), its largest connected component \(C\) and the mixing time of a random walk on \(C\) are investigated. The diameter of \(C\) and the mixing time are specified for \(p\) in the vicinity of \(1/n\). Generalizations to graphs with bounded degrees are also considered.

Recommendations

• Mixing time of near-critical random graphs
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• Random walks on the random graph
• The mixing time of the giant component of a random graph
• Comparing mixing times on sparse random graphs

Cites work

• Brownian excursions, critical random graphs and the multiplicative coalescent
• Critical percolation on random regular graphs
• Galton-Watson trees with the same mean have the same polar sets
• scientific article; zbMATH DE number 3163289 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3978019 (Why is no real title available?)
• scientific article; zbMATH DE number 1380601 (Why is no real title available?)
• scientific article; zbMATH DE number 1418385 (Why is no real title available?)
• scientific article; zbMATH DE number 3255217 (Why is no real title available?)
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Random subgraphs of the 2D Hamming graph: The supercritical phase
• Random walk on the incipient infinite cluster on trees
• Random walks and the effective resistance of networks
• Random walks, capacity and percolation on trees
• The critical random graph, with martingales
• The diameter of sparse random graphs
• The diameter of sparse random graphs
• The electrical resistance of a graph captures its commute and cover times
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The mixing time of the giant component of a random graph
• The phase transition in inhomogeneous random graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The Structure of a Random Graph at the Point of the Phase Transition

Cited in

(48)

• The Alexander-Orbach conjecture holds in high dimensions
• Mixing times of random walks on dynamic configuration models
• Exceptional times of the critical dynamical Erdős-Rényi graph
• The largest component in critical random intersection graphs
• Cutoff for lamplighter chains on fractals
• Mixing properties for hom-shifts and the distance between walks on associated graphs
• Critical random graphs and the differential equations technique
• Random walks on the random graph
• On the critical probability in percolation
• Geometry of the minimal spanning tree of a random 3-regular graph
• Global lower mass-bound for critical configuration models in the heavy-tailed regime
• Cutoff for random lifts of weighted graphs
• Internal DLA on cylinder graphs: fluctuations and mixing
• Random walk on the high-dimensional IIC
• Random walk on sparse random digraphs
• The continuum limit of critical random graphs
• Scaling window for mean-field percolation of averages
• Diameters of random circulant graphs
• Unlacing hypercube percolation: a survey
• On the tree-depth of random graphs
• Mean-field conditions for percolation on finite graphs
• Critical percolation on scale-free random graphs: new universality class for the configuration model
• The mixing time of the giant component of a random graph
• Mixing time of molecules inside of nanoporous gold
• The evolution of the cover time
• Critical percolation on random regular graphs
• Anatomy of a Young giant component in the random graph
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• Long-Range Percolation Mixing Time
• Cycle structure of percolation on high-dimensional tori
• Random subshifts of finite type
• Mixing time of near-critical random graphs
• Convergence of mixing times for sequences of random walks on finite graphs
• Critical percolation on random regular graphs
• Diameters in supercritical random graphs via first passage percolation
• The diameter of sparse random graphs
• Hypercube percolation
• Expansion of Percolation Critical Points for Hamming Graphs
• Universal finite-size scaling for percolation theory in high dimensions
• The critical window in random digraphs
• Distances in \(\frac{1}{\|x-y\|^{2d}}\) percolation models for all dimensions
• Extremal regime for one-dimensional Mott variable-range hopping
• A random walk on the Rado graph
• Random graph asymptotics on high-dimensional tori. II: volume, diameter and mixing time
• A branching process with deletions and mergers that matches the threshold for hypercube percolation
• A note about critical percolation on finite graphs
• Linear colouring of binomial random graphs
• Behavior of the distance exponent for \(\frac{1}{|x-y|^{2d}}\) long-range percolation

This page was built for publication: Critical random graphs: Diameter and mixing time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q941296)