Diameters in supercritical random graphs via first passage percolation

Details Diameters in supercritical random graphs via first passage percolation Diameters in supercritical random graphs via first passage percolation

2009-06-10

arxiv.org/abs/0906.1840v2

Mathematics

Combinatorics

25 pages; to appear in Combinatorics, Probability and Computing

Scientific paper

We study the diameter of $C_1$, the largest component of the Erd\H{o}s-R\'enyi random graph $G(n,p)$ in the emerging supercritical phase, 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. Prior to this work, Riordan and Wormald gave precise estimates on the diameter, however these did 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 differed by a factor of $1000/7$. We show that throughout the emerging supercritical phase, i.e. for any $\epsilon=o(1)$ with $\epsilon^3 n \to \infty$, the diameter of $C_1$ is with high probability asymptotic to $D(\epsilon,n)=(3/\epsilon)\log(\epsilon^3 n)$. This constitutes the first proof of the asymptotics of the diameter valid throughout this phase. The proof relies 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. The main advantage of our method is its flexibility. It also implies that in the emerging supercritical phase the diameter of the 2-core of $C_1$ is w.h.p. asymptotic to $(2/3)D(\epsilon,n)$, and the maximal distance in $C_1$ between any pair of kernel vertices is w.h.p. asymptotic to $(5/9)D(\epsilon,n)$.

Affiliated with

Also associated with

No associations

Rating

Diameters in supercritical random graphs via first passage percolation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Diameters in supercritical random graphs via first passage percolation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Diameters in supercritical random graphs via first passage percolation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-206203