| Diameters in supercritical random graphs via first passage percolation (2009) | |||||||||
Abstract | |||||||||
| We study the diameter of $C_1$, the largest component of the Erd\H{o}s-R\'enyi random graph $\cG(n,p)$ emerging from the critical window, i.e., for $p = \frac{1+\epsilon}n$ where $\epsilon^3 n \to \infty$ and $\epsilon=o(1)$. This parameter was extensively studied for fixed $\epsilon > 0$, yet results for $\epsilon=o(1)$ outside the critical window were only obtained very recently: Riordan and Wormald gave precise estimates on the diameter, however these do not cover the entire supercritical regime (namely, when $\epsilon^3 n\to\infty$ arbitrarily slowly); {\L}uczak and Seierstad estimated its order throughout this regime, yet their upper and lower bounds differ by a factor of $\frac{1000}7$. We show that for any $\epsilon=o(1)$ with $\epsilon^3n\to\infty$, the diameter of $C_1$ is with high probability asymptotic to $D (\epsilon,n)=(3/\epsilon)\log(\epsilon^3 n)$. We also prove that, in this regime, the diameter of the 2-core of $C_1$ is w.h.p. asymptotic to $\frac23 D(\epsilon,n)$, and the maximal distance in it between any pair of kernel vertices is w.h.p. asymptotic to $\frac{5}9D(\epsilon,n)$. The proofs rely on a recent structure result for the supercritical giant component, which reduces the problem of estimating distances between its vertices to the study of passage times in first-passage percolation.. Comment: 23 pages | |||||||||
Publication details | |||||||||
| |||||||||