Diameters in Supercritical Random Graphs Via First Passage Percolation

Abstract

We study the diameter of 1 , the largest component of the Erdős–Rényi random graph ( n , p ) in the emerging supercritical phase, i.e. , for p = $\frac{1+\epsilon}n$ where ε 3 n → ∞ and ε = o (1). This parameter was extensively studied for fixed ε > 0, yet results for ε = 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 ε 3 n → ∞ arbitrarily slowly). Łuczak and Seierstad estimated its order throughout this regime, yet their upper and lower bounds differed by a factor of $\frac{1000}7$ . We show that throughout the emerging supercritical phase, i.e. , for any ε = o (1) with ε 3 n → ∞, the diameter of 1 is with high probability asymptotic to D (ε, n ) = (3/ε)log(ε 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 1 is w.h.p. asymptotic to $\frac23 D(\epsilon,n)$ , and the maximal distance in 1 between any pair of kernel vertices is w.h.p. asymptotic to $\frac{5}9D(\epsilon,n)$ .

Locations

• arXiv (Cornell University) - View - PDF
• Combinatorics Probability Computing - View