Diameter of the Stochastic Mean-Field Model of Distance

Source abstract

We consider the complete graph 𝜅 n on n vertices with exponential mean n edge lengths. Writing C ij for the weight of the smallest-weight path between vertices i, j ∈ [ n ], Janson [18] showed that max i,j ∈[ n ] C ij /log n converges in probability to 3. We extend these results by showing that max i,j ∈[ n ] C ij − 3 log n converges in distribution to some 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-centred graph diameter of the barely supercritical Erdős–Rényi random graph in [22].