Diameters in Supercritical Random Graphs Via First Passage Percolation

作者：Ding Jian^*; Kim Jeong Han; Lubetzky Eyal; Peres Yuval

来源：Combinatorics Probability & Computing, 2010, 19(5-6): 729-751.

DOI：10.1017/S0963548310000301

We study the diameter of C(1), the largest component of the Erdos-Renyi random graph G(n, p) in the emerging supercritical phase, i.e., for p = 1+epsilon/n where epsilon(3)n -> infinity 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 -> infinity arbitrarily slowly). Luczak 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 -> infinity, 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).

• 出版日期2010-11
• 单位Microsoft