Diameter of the stochastic mean-field model of distance

preprint2013arXivOpen access

Abstract

We consider the complete graph $\cK_n$ on nn vertices with exponential mean nn edge lengths. Writing CijC_{ij} for the weight of the smallest-weight path between vertex i,j∈[n]i,j\in [n], Janson showed that max⁡i,j∈[n]Cij/log⁡n\max_{i,j\in [n]} C_{ij}/\log{n} converges in probability to 3. We extend this result by showing that max⁡i,j∈[n]Cij−3log⁡n\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.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.