The diameter of sparse random graphs

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.

92 pages; expanded slightly with minor corrections; to appear in Combinatorics, Probability and Computing

References in corpus (1)

• Critical random graphs: Diameter and mixing time

Cited by in corpus (11)

• Robustness of Noisy Quantum Networks
• Analytical results for the distribution of shortest path lengths in random networks
• The diameter of weighted random graphs
• Mixing time of near-critical random graphs
• Bounds for list-decoding and list-recovery of random linear codes
• Strong noise sensitivity and random graphs
• The mean and variance of the distribution of shortest path lengths of random regular graphs
• On the diameter of hyperbolic random graphs
• Shotgun assembly of labeled graphs
• Limiting shape of the Depth First Search tree in an Erdős-Rényi graph
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks