Critical random graphs: Diameter and mixing time

Abstract

Let ${\mathcal{C}}_1$ denote the largest connected component of the critical Erdős--Rényi random graph $G(n,\frac{1}{n})$. 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)\le 1+O(n^{-1/3})$.

Published in at http://dx.doi.org/10.1214/07-AOP358 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (7)

• The phase transition in inhomogeneous random graphs
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• The mixing time of the giant component of a random graph
• The Evolution of the Mixing Rate
• The critical random graph, with martingales
• Random subgraphs of the 2D Hamming graph: the supercritical phase
• Critical percolation on random regular graphs

Cited by in corpus (44)

• The Alexander-Orbach conjecture holds in high dimensions
• Controllability of multiplex, multi-timescale networks
• The diameter of sparse random graphs
• Random graph asymptotics on high-dimensional tori. II. Volume, diameter and mixing time
• Critical percolation clusters in seven dimensions and on a complete graph
• Universal Finite-Size Scaling for Percolation Theory in High Dimensions
• Mixing time of near-critical random graphs
• Mixing times for the interchange process
• Moduli of continuity of local times of random walks on graphs in terms of the resistance metric
• On the critical probability in percolation
• Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
• Percolation effects in the Fortuin-Kasteleyn Ising model on the complete graph
• Cover times for sequences of reversible Markov chains on random graphs
• Shotgun assembly of labeled graphs
• Expansion of percolation critical points for Hamming graphs
• Distances in $\frac{1}{|x-y{|}^{2d}}$ percolation models for all dimensions
• 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
• The continuum limit of critical random graphs
• Random subshifts of finite type
• Bounds for the annealed return probability on large finite percolation clusters
• Critical Percolation on Random Networks with Prescribed Degrees
• Scaling window for mean-field percolation of averages
• Diameters in supercritical random graphs via first passage percolation
• Diameters of random circulant graphs
• Unlacing the lace expansion: a survey to hypercube percolation
• Convex minorant trees associated with Brownian paths and the continuum limit of the minimum spanning tree
• Behavior of the distance exponent for $\frac{1}{|x-y{|}^{2d}}$ long-range percolation
• Faster quantum mixing of Markov chains in non-regular graph with fewer qubits
• Isoperimetric lower bounds for critical exponents for long-range percolation
• Cycle structure of percolation on high-dimensional tori
• Slightly subcritical hypercube percolation
• The diameter of Inhomogeneous random graphs
• Critical percolation on random regular graphs
• A note on percolation on Z^d: isoperimetric profile via exponential cluster repulsion
• Graph-Theoretic Analysis of Belief System Dynamics under Logic Constraints
• A note about critical percolation on finite graphs
• The giant in random graphs is almost local
• Extremal regime for one-dimensional Mott variable-range hopping
• A branching process with deletions and mergers that matches the threshold for hypercube percolation
• Scaling limit for the random walk on the largest connected component of the critical random graph
• Sensitivity of mixing times
• Random walk on the high-dimensional IIC
• Convergence of mixing times for sequences of random walks on finite graphs