Universality for first passage percolation on sparse random graphs (Q2406570)

This paper considers first passage percolation on random graphs given by the configuration model. That is, for a given such graph with \(n\) vertices, edges of the graph are assigned weights, which in this paper are assumed to be independent and identical distributed. Moreover, the common distribution of the edge weights is assumed to be continuous so that, between any two vertices, there is almost surely a unique path of minimal weight. This is called the optimal path. Under the assumption that the degree distribution of the configuration model satisfies a uniform \(X^2\log X\)-condition (which implies that the graph is sparse), the following statements are proven for the optimal path between a pair of two randomly chosen vertices, denoted by \(L_n\): \(1.\) For some sequence \(\alpha_n\), we have that \(L_n - \log(n)/ \alpha_n\) converges to a limiting random variable. \(2.\) The hopcount, that is, the number of edges on the optimal path \(L_n\), satisfies a central limit theorem (CLT) with asymptotic mean and variance of order \(\log(n)\). Furthermore, ``the sequence \(\alpha_n\) and the norming constants for the CLT are expressible in terms of the parameters of an associated continuous-time branching process that describes the growth of neighborhoods around a uniformly chosen vertex in the random graph. The limit of \(L_n - \log(n)/ \alpha_n\) equals the sum of the logarithm of the product of two independent martingale limits, and a Gumbel random variable.'' These results extend on previous work by the same authors [Ann.\ Appl.\ Probab.\ 20, No.\ 5, 1907--1965 (2010; Zbl 1212.60157)] where only exponential distributed edge weights were considered. ``The proofs in the paper rely on a refined coupling between shortest path trees and continuous-time branching processes, and on a Poisson point process limit for the occurrence of short paths between two randomly chosen vertices.''