Answers are grounded in this paper and cite their sources.
Give the edges of the complete graph on n vertices independent exponential weights and let Mₙ be the largest number of edges of a minimum-weight path between two vertices. Addario-Berry, Broutin and Lugosi proved that Mₙ/log n→α in probability, where α≈3.5911 solves αlogα-α=1, with the bounds αlog n-Lloglog n≤ Mₙ≤αlog n+ω(n). We prove that P(Mₙ≥ bₙ+x)≤ Cα⁻ˣ for all x≥0, where bₙ=αlog n-(loglog n)/(2logα). Hence Mₙ-αlog n→-∞ in probability and E Mₙ≤ bₙ+O(1). We also find the asymptotic value of the expected number of pairs of vertices joined by a minimum-weight path of at least k edges when k=αlog n+O(loglog n), show that at k= bₙ the second moment of this number tends to infinity although its mean stays bounded, and prove that P(Mₙ=n-1)=n/(2\,(n-1)!) for every n≥2. The lower side of the question of van der Hofstad on the fluctuations of Mₙ stays open.
No takes yet. Share an insight, caveat, or question.
Yitzchak Shmalo (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: