# The diameter of sparse random graphs

Riordan, O
Wormald, N

2010

## Journal:

Combinatorics, Probability and Computing 19 (2010), 835--926

## Last Updated:

2020-10-05T03:19:59.85+01:00

5-6

19

## DOI:

10.1017/S0963548310000325

835-926

## abstract:

In this paper we study the diameter of the random graph $G(n,p)$, i.e., the
the largest finite distance between two vertices, for a wide range of functions
$p=p(n)$. For $p=\la/n$ with $\la>1$ constant, we give a simple proof of an
essentially best possible result, with an $O_p(1)$ additive correction term.
Using similar techniques, we establish 2-point concentration in the case that
$np\to\infty$. For $p=(1+\epsilon)/n$ with $\epsilon\to 0$, we obtain a
corresponding result that applies all the way down to the scaling window of the
phase transition, with an $O_p(1/\epsilon)$ additive correction term whose
(appropriately scaled) limiting distribution we describe. Combined with earlier
results, our new results complete the determination of the diameter of the
random graph $G(n,p)$ to an accuracy of the order of its standard deviation (or
better), for all functions $p=p(n)$. Throughout we use branching process
methods, rather than the more common approach of separate analysis of the
2-core and the trees attached to it.

107111