### Abstract

We study the diameter of C1, the largest component of the Erdos-Rényi random graph G(n, p) in the emerging supercritical phase, i.e., for p = 1+ε/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 1000/7. We show that throughout the emerging supercritical phase, i.e., for any ε = o(1) with ε^{3}n → ∞, the diameter of C1 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 C1 is w.h.p. asymptotic to 2/3 D(ε,n), and the maximal distance in 1 between any pair of kernel vertices is w.h.p. asymptotic to 5/9D(ε,n).

Original language | English (US) |
---|---|

Pages (from-to) | 729-751 |

Number of pages | 23 |

Journal | Combinatorics Probability and Computing |

Volume | 19 |

Issue number | 5-6 |

DOIs | |

State | Published - Sep 2010 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Diameters in supercritical random graphs via first passage percolation'. Together they form a unique fingerprint.

## Cite this

*Combinatorics Probability and Computing*,

*19*(5-6), 729-751. https://doi.org/10.1017/S0963548310000301