Diameter of the Stochastic Mean-Field Model of Distance. (7th August 2017)

• Record Type: Journal Article
• Authors: BHAMIDI, SHANKAR; VAN DER HOFSTAD, REMCO
• Is Part Of: Combinatorics, probability and computing. Volume 26:Number 6(2017:Nov.)
• Page Start: 797
• Page End: 825
• Publication Date: 2017-08-07
• Subjects: Primary 60C05, -- Secondary 05C80, -- 90B15; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548317000232
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : We consider the complete graph 𝜅n on n vertices with exponential mean n edge lengths. Writing Cij 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 ] Cij − 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].