Diameter of the stochastic mean-field model of distance

Research output: Book/ReportReportAcademic

152 Downloads (Pure)

Abstract

We consider the complete graph K_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 [17] showed that max_{i,j \in [n]} C_{ij} / log n converges in probability to 3. We extend this results by showing that max_{i,j \in [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-centered graph diameter of the barely supercritical Erdös-Rényi random graph in [21].
Original languageEnglish
Place of PublicationEindhoven
PublisherEurandom
Number of pages27
Publication statusPublished - 2013

Publication series

NameReport Eurandom
Volume2013013
ISSN (Print)1389-2355

Fingerprint

Dive into the research topics of 'Diameter of the stochastic mean-field model of distance'. Together they form a unique fingerprint.

Cite this