Long paths in first passage percolation on the complete graph. I: Local PWIT dynamics. (English) Zbl 1459.60196

Eckhoff, Maren; Goodman, Jesse; van der Hofstad, Remco; Nardi, Francesca R.

Electron. J. Probab. 25, Paper No. 81, 45 p. (2020).

Summary: We study the random geometry of first passage percolation on the complete graph equipped with independent and identically distributed edge weights. We find classes with different behaviour depending on a sequence of parameters \((s_n)_{n\geq 1}\) that quantifies the extreme-value behavior of small weights. We consider both \(n\)-independent as well as \(n\)-dependent edge weights and illustrate our results in many examples.
In particular, we investigate the case where \(s_n \to \infty\), and focus on the exploration process that grows the smallest-weight tree from a vertex. We establish that the smallest-weight tree process locally converges to the invasion percolation cluster on the Poisson-weighted infinite tree, and we identify the scaling limit of the weight of the smallest-weight path between two uniform vertices. In addition, we show that over a long time interval, the growth of the smallest-weight tree maintains the same volume-height scaling exponent – volume proportional to the square of the height – found in critical Galton – Watson branching trees and critical Erdős-Rényi random graphs.

MSC:

60K35	Interacting random processes; statistical mechanics type models; percolation theory
60J80	Branching processes (Galton-Watson, birth-and-death, etc.)
60G55	Point processes (e.g., Poisson, Cox, Hawkes processes)

Keywords:

first passage percolation; invasion percolation; random graphs

References:

[1]	Louigi Addario-Berry, The local weak limit of the minimum spanning tree of the complete graph, Preprint: arXiv:1301.1667v2 [math.PR], 2013. · Zbl 1278.60128 · doi:10.1214/12-AOP758
[2]	Louigi Addario-Berry, Nicolas Broutin, Christina Goldschmidt, and Grégory Miermont, The scaling limit of the minimum spanning tree of the complete graph, Ann. Probab. 45 (2017), no. 5, 3075-3144. · Zbl 1407.60013 · doi:10.1214/16-AOP1132
[3]	Louigi Addario-Berry, Nicolas Broutin, and Bruce Reed, Critical random graphs and the structure of the minimal spanning tree, Random Struct. Algor. 35 (2008), no. 3, 323-347. · Zbl 1190.05042
[4]	Louigi Addario-Berry, Simon Griffiths, and Ross J. Kang, Invasion percolation on the Poisson-weighted infinite tree, Ann. Appl. Probab. 22 (2012), no. 3, 931-970. · Zbl 1262.60091 · doi:10.1214/11-AAP761
[5]	David Aldous, The continuum random tree. I, Ann. Probab. 19 (1991), no. 1, 1-28. · Zbl 0722.60013 · doi:10.1214/aop/1176990534
[6]	David Aldous, The continuum random tree. III, Ann. Probab. 21 (1993), no. 1, 248-289. · Zbl 0791.60009 · doi:10.1214/aop/1176989404
[7]	David Aldous and J. Michael Steele, The objective method: probabilistic combinatorial optimization and local weak convergence, Probability on Discrete Structures, Encyclopaedia of Mathematical Sciences, vol. 110, Springer, Berlin, 2004, pp. 1-72. · Zbl 1037.60008
[8]	Omer Angel, Jesse Goodman, Frank den Hollander, and Gordon Slade, Invasion percolation on regular trees, Ann. Probab. 36 (2008), no. 2, 420-466. · Zbl 1145.60050 · doi:10.1214/07-AOP346
[9]	Itai Benjamini and Oded Schramm, Recurrence of distributional limits of finite planar graphs, Electron. J. Probab. 6 (2001), no. 23, 1-13. · Zbl 1010.82021
[10]	Shankar Bhamidi and Remco van der Hofstad, Weak disorder asymptotics in the stochastic mean-field model of distance, Ann. Appl. Probab. 22 (2012), no. 1, 29-69. · Zbl 1248.60012
[11]	Shankar Bhamidi and Remco van der Hofstad, Diameter of the stochastic mean-field model of distance, Combin. Probab. Comput. 26 (2017), no. 6, 797-825. · Zbl 1379.60008
[12]	Shankar Bhamidi, Remco van der Hofstad, and Gerard Hooghiemstra, Weak disorder in the stochastic mean-field model of distance II, Bernoulli 19 (2013), no. 2, 363-386. · Zbl 1279.60018
[13]	Michael Damron and Artëm Sapozhnikov, Outlets of 2D invasion percolation and multiple-armed incipient infinite clusters, Probab. Theory Rel. Fields 150 (2011), no. 1-2, 257-294. · Zbl 1225.82030 · doi:10.1007/s00440-010-0274-y
[14]	Maren Eckhoff, Jesse Goodman, Remco van der Hofstad, and Francesca R. Nardi, Long paths in first passage percolation on the complete graph II. Global branching dynamics, to appear in J. Stat. Phys. DOI:10.1007/s10955-020-02585-1. · Zbl 1460.60106
[15]	Maren Eckhoff, Jesse Goodman, Remco van der Hofstad, and Francesca R. Nardi, Short paths for first passage percolation on the complete graph, J. Stat. Phys. 151 (2013), 1056-1088. · Zbl 1314.82021 · doi:10.1007/s10955-013-0743-7
[16]	Daniel Fernholz and Vijaya Ramachandran, The diameter of sparse random graphs, Random Structures Algorithms 31 (2007), no. 4, 482-516. · Zbl 1129.05046 · doi:10.1002/rsa.20197
[17]	Jesse Goodman, Exponential growth of ponds in invasion percolation on regular trees, J. Stat. Phys. 147 (2012), 919-941. · Zbl 1246.82047 · doi:10.1007/s10955-012-0509-7
[18]	Theodore E. Harris, The theory of branching processes, Die Grundlehren der Mathematischen Wissenschaften, Bd. 119, Springer-Verlag, Berlin, 1963. · Zbl 1037.60001
[19]	Remco van der Hofstad, Random graphs and complex networks. Vol. 1, Cambridge Series in Statistical and Probabilistic Mathematics, [43], Cambridge University Press, Cambridge, 2017. · Zbl 1361.05002
[20]	Svante Janson, One, two and three times \(\log n/n\) for paths in a complete graph with random weights, Comb. Probab. Comput. 8 (1999), no. 4, 347-361. · Zbl 0934.05115
[21]	Daniel L.