2023/11/27 by Remco van der Hofstad, van der Hofstad, Remco, Bas Lodewijks +1
Mathematics · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Mathematics #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics
paper · pdf · doi:10.48550/arxiv.2311.16088
openalex publication_date 2023/11/27 · openalex created_date 2023/11/29 · openalex updated_date 2026/08/01
We study a geometric version of first-passage percolation on the complete graph, known as long-range first-passage percolation. Here, the vertices of the complete graph \mathcal Kn are embedded in the d-dimensional torus \mathbb Tnd, and each edge e is assigned an independent transmission time Te=‖e‖\mathbb TndαEe, where Ee is a rate-one exponential random variable associated with the edge e, ‖⋅‖\mathbb Tnd denotes the torus-norm, and α≥0 is a parameter. We are interested in the case α∈[0,d), which corresponds to the instantaneous percolation regime for long-range first-passage percolation on \mathbb Zd studied by Chatterjee and Dey, and which extends first-passage percolation on the complete graph (the α=0 case) studied by Janson. We consider the typical distance, flooding time, and diameter of the model. Our results show a 1,2,3-type result, akin to first-passage percolation on the complete graph as shown by Janson. The results also provide a quantitative perspective to the qualitative results observed by Chatterjee and Dey on \mathbb Zd.