First passage percolation on the Erdös-Rényi random graph

In this paper we explore ¿rst passage percolation (FPP) on the Erdös-Rényi random graph Gn(pn), where each edge is given an independent exponential edge weight with rate 1. In the sparse regime, i.e., when npn ¿ ¿ > 1, we ¿nd re¿ned asymptotics both for the minimal weight of the path between uniformly chosen vertices in the giant component, as well as for the hopcount (i.e., the number of edges) on this minimal weight path. More precisely, we prove a central limit theorem for the hopcount, with asymptotic mean and variance both equal to ¿/(¿ - 1) log n. Furthermore, we prove that the minimal weight centered by log n/(¿ - 1) converges in distribution. We also investigate the dense regime, where npn ¿ 8. We ¿nd that although the base graph is a ultra small (meaning that graph distances between uniformly chosen vertices are o(log n)), attaching random edge weights changes the geometry of the network completely. Indeed, the hopcount Hn satis¿es the universality property that whatever be the value of pn, Hn/ log n ¿ 1 in probability and, more precisely, (Hn-ßn log n)/ v log n, where ßn = ¿n/(¿n- 1), has a limiting standard normal distribution. The constant ßn can be replaced by 1 precisely when ¿n » v log n, a case that has appeared in the literature (under stronger conditions on ¿n) in [2, 12]. We also ¿nd bounds for the maximal weight and maximal hopcount between vertices in the graph. This paper continues the investigation of FPP initiated in [2] and [3]. Compared to the setting on the con¿guration model studied in [3], the proofs presented here are much simpler due to a direct relation between FPP on the Erdös-Rényi random graph and thinned continuous-time branching processes