The diameter of sparse random graphs

Author: 

Riordan, O
Wormald, N

Publication Date: 

2010

Journal: 

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

Last Updated: 

2020-06-07T02:35:06.81+01:00

Issue: 

5-6

Volume: 

19

DOI: 

10.1017/S0963548310000325

page: 

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.

Symplectic id: 

107111

Download URL: 

Submitted to ORA: 

Not Submitted

Publication Type: 

Journal Article