Diameter of the stochastic mean-field model of distance

Abstract

We consider the complete graph $\cK_n$ on $n$ vertices with exponential mean $n$ edge lengths. Writing $C_{ij}$ for the weight of the smallest-weight path between vertex $i,j\in [n]$, Janson showed that ${\max }_{i,j\in [n]}{C}_{ij}/\log n$ converges in probability to 3. We extend this result by showing that ${\max }_{i,j\in [n]}{C}_{ij}-3\log n$ converges in distribution to a limiting random variable that can be identified via a maximization procedure on a limiting infinite random structure. Interestingly, this limiting random variable has also appeared as the weak limit of the re-centered graph diameter of the barely supercritical Erdős-Rényi random graph in work by Riordan and Wormald.

arXiv comment27 pages