Critical random graphs: Diameter and mixing time

By Asaf Nachmias, Yuval Peres. 2007

117 citations recorded by the source corpus.

Let $\mathcal{C}_{1}$ denote the largest connected component of the critical Erdős–Renyi random graph $G(n,{\frac{1}{n}})$. We show that, typically, the diameter of $\mathcal{C}_{1}$ is of order n1/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 n2/3 of p-bond percolation on any d-regular n-vertex graph where such clusters exist, provided that p(d−1)≤1+O(n−1/3).

Subfields: Mathematical Physics, Statistical and Nonlinear Physics, Statistics and Probability

View Paper: https://www.semanticscholar.org/paper/dbffa78fd05e08003c08277885d2169ff83c0408

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Physics

In Statistical and Nonlinear Physics

In Statistics and Probability

Citations in the corpus

The continuum limit of critical random graphs (2009, result): “For our purposes, the latter bounds are most usefully stated by Nachmias and Peres [42] (see also [44, 50]).”
A note on percolation on $Z^d$: isoperimetric profile via exponential cluster repulsion (2007, unknown): “Therefore, P ( |Sfull(·, Y, Z)| ≤ εkfull ∣ ∣ ∣ (X,Y,Z) ∈ Sfull ) = ∑ j≤εkfull jP(ξfull = j) Eξfull ≤ εP(ξfull ≤ εkfull) ≤ ε , for any ε > 0.”
Random walk on sparse random digraphs (2015, methodology): “Bounds for the mixing time on the largest component of the popular Erdős–Renyi model have also been obtained by various authors, in both the critical and super-critical connectivity regime [7,23,24,35].”
Random Graphs and Complex Networks (2016, background): “Add results in NacPer07b [164] on diameter of critical random graph in notes.”
Random walks on the random graph (2015, background): “…chain analysis became suﬃciently developed to give the typical order of the mixing time of random walk, which transitions from n in the critical window ([24]) to log 2 n at p = on for λ > 1 ﬁxed ([2,13]) through the interpolating order ε − 3 log 2 ( ε 3 n ) when p = 1+ for n − 1 / 3 ε 1 ([8]).”
The Alexander-Orbach conjecture holds in high dimensions (2008, background): “We are indebted to Yuval Peres for suggesting the use of Γ instead of H in Theorem 1.2.”