Critical random graphs: Diameter and mixing time

DOI10.1214/07-AOP358zbMath1160.05053arXivmath/0701316OpenAlexW2014075779MaRDI QIDQ941296

Yuval Peres, Asaf Nachmias

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

Random walkRandom graphConnected componentPercolationMixing time

Mathematics Subject Classification ID

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

Related Items

Mixing times of random walks on dynamic configuration models, The largest component in critical random intersection graphs, Mean-field conditions for percolation on finite graphs, The mixing time of the giant component of a random graph, Cutoff for lamplighter chains on fractals, Critical percolation on scale-free random graphs: new universality class for the configuration model, Random walk on sparse random digraphs, Cycle structure of percolation on high-dimensional tori, Random subshifts of finite type, The continuum limit of critical random graphs, 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, Mixing time of near-critical random graphs, Scaling window for mean-field percolation of averages, Random graph asymptotics on high-dimensional tori. II: volume, diameter and mixing time, Diameters of random circulant graphs, Unlacing hypercube percolation: a survey, On the tree-depth of random graphs, A note about critical percolation on finite graphs, The Evolution of the Cover Time, Random walks on the random graph, On the critical probability in percolation, Diameters in Supercritical Random Graphs Via First Passage Percolation, The Diameter of Sparse Random Graphs, Hypercube percolation, Random walk on the high-dimensional IIC, Critical percolation on random regular graphs, Geometry of the minimal spanning tree of a random 3-regular graph, Expansion of Percolation Critical Points for Hamming Graphs, Anatomy of a young giant component in the random graph, The Alexander-Orbach conjecture holds in high dimensions, Global lower mass-bound for critical configuration models in the heavy-tailed regime, Universal finite-size scaling for percolation theory in high dimensions, Critical percolation on random regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Random walks and the effective resistance of networks
• The critical random graph, with martingales
• Random walks, capacity and percolation on trees
• Brownian excursions, critical random graphs and the multiplicative coalescent
• The electrical resistance of a graph captures its commute and cover times
• Galton-Watson trees with the same mean have the same polar sets
• Random subgraphs of the 2D Hamming graph: The supercritical phase
• Random walk on the incipient infinite cluster on trees
• The mixing time of the giant component of a random graph
• Critical percolation on random regular graphs
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The Structure of a Random Graph at the Point of the Phase Transition
• The phase transition in inhomogeneous random graphs
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• The diameter of sparse random graphs
• The diameter of sparse random graphs