Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T22:24:13.463Z Has data issue: false hasContentIssue false
  • English
  • Français

Diameter of the Stochastic Mean-Field Model of Distance

Part of:Graph theoryOperations research and management scienceCombinatorial probability

Published online by Cambridge University Press:  07 August 2017

SHANKAR BHAMIDI and
REMCO VAN DER HOFSTAD
SHANKAR BHAMIDI
Affiliation:
Department of Statistics, University of North Carolina, Chapel Hill, NC 27599, USA (e-mail: bhamidi@email.unc.edu)
REMCO VAN DER HOFSTAD
Affiliation:
Department of Mathematics and Computer Science, Eindhoven University of Technology, PO Box 513, 5600 MB Eindhoven, The Netherlands (e-mail: rhofstad@win.tue.nl)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 maxi,j∈[n]C ij/logn converges in probability to 3. We extend these results by showing that maxi,j∈[n]Cij − 3 logn 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].

MSC classification

Primary:60C05: Combinatorial probability
Secondary:05C80: Random graphs90B15: Network models, stochastic

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 6 , November 2017, pp. 797 - 825
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Addario-Berry, L. Broutin, N. and Lugosi, G. (2010) The longest minimum-weight path in a complete graph. Combin. Probab. Comput. 19 1–19.CrossRefGoogle Scholar
[2] Aldous, D. (1992) Asymptotics in the random assignment problem. Probab. Theory Rel. Fields 93 507–534.Google Scholar
[3] Aldous, D. J. (2001) The ζ (2) limit in the random assignment problem. Random Struct. Alg. 18 381–418.Google Scholar
[4] Aldous, D. J. (2010) More uses of exchangeability: Representations of complex random structures. In Probability and Mathematical Genetics: Papers in Honour of Sir John Kingman (Bingham, N. H. and Goldie, C. M., eds), London Mathematical Society Lecture Note Series, Cambridge University Press, pp. 35–63.Google Scholar
[5] Aldous, D. J. and Bhamidi, S. (2010) Edge flows in the complete random-lengths network. Random Struct. Alg. 37 271–311.Google Scholar
[6] Aldous, D. and Steele, J. M. (2004) The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures (Kesten, H., ed.), Vol. 110 of Encyclopaedia of Mathematical Sciences, Springer, pp. 1–72.Google Scholar
[7] Amini, H. and Lelarge, M. (2015) The diameter of weighted random graphs. Ann. Appl. Probab. 25 1686–1727.Google Scholar
[8] Amini, H. and Peres, Y. (2014) Shortest-weight paths in random regular graphs. SIAM J. Discrete Math. 28 656–672.Google Scholar
[9] Barbour, A. D., Holst, L. and Janson, S. (1992) Poisson Approximation, Vol. 2 of Oxford Studies in Probability, The Clarendon Press, Oxford University Press.CrossRefGoogle Scholar
[10] Bhamidi, S. (2008) First passage percolation on locally treelike networks I: Dense random graphs. J. Math. Phys. 49 125218.Google Scholar
[11] Bhamidi, S., van der Hofstad, R. and Hooghiemstra, G. (2010) First passage percolation on random graphs with finite mean degrees. Ann. Appl. Probab. 20 1907–1965.Google Scholar
[12] Devroye, L. (1987) Branching processes in the analysis of the heights of trees. Acta Informatica 24 277–298.CrossRefGoogle Scholar
[13] Ding, J., Kim, J. H., Lubetzky, E. and Peres, Y. (2010) Diameters in supercritical random graphs via first passage percolation. Combin. Probab. Comput. 19 729–751.Google Scholar
[14] Ding, J., Kim, J. H., Lubetzky, E. and Peres, Y. (2011) Anatomy of a young giant component in the random graph. Random Struct. Alg. 39 139–178.CrossRefGoogle Scholar
[15] Frieze, A. M. (1985) On the value of a random minimum spanning tree problem. Discrete Appl. Math. 10 47–56.CrossRefGoogle Scholar
[16] Goldstein, L. and Rinott, Y. (2007) Functional BKR inequalities, and their duals, with applications. J. Theoret. Probab. 20 275–293.Google Scholar
[17] Janson, S. (1995) The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph. Random Struct. Alg. 7 337–355.Google Scholar
[18] Janson, S. (1999) One, two and three times log n/n for paths in a complete graph with random weights. Combin. Probab. Comput. 8 347–361.Google Scholar
[19] Kemperman, J. H. B. (1977) On the FKG-inequality for measures on a partially ordered space. Indag. Math. 39 313–331.Google Scholar
[20] Kingman, J. F. C. (1993) Poisson Processes, Vol. 3 of Oxford Studies in Probability, The Clarendon Press, Oxford University Press.Google Scholar
[21] Pittel, B. (1994) Note on the heights of random recursive trees and random m-ary search trees. Random Struct. Alg. 5 337–347.Google Scholar
[22] Riordan, O. and Wormald, N. (2010) The diameter of sparse random graphs. Combin. Probab. Comput. 19 835–926.CrossRefGoogle Scholar
[23] Salez, J. (2013) Joint distribution of distances in large random regular networks. J. Appl. Probab. 50 861–870.Google Scholar
[24] Smythe, R. T. and Mahmoud, H. M. (1994) A survey of recursive trees. Teor. Ĭmovīr. Mat. Stat. 51 1–29.Google Scholar
[25] Wästlund, J. (2010) The mean field traveling salesman and related problems. Acta Mathematica 204 91–150.CrossRefGoogle Scholar