{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:13:31Z","timestamp":1772118811697,"version":"3.50.1"},"reference-count":17,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T00:00:00Z","timestamp":1308528000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2011,9]]},"abstract":"<jats:p>In this paper we explore first passage percolation (FPP) on the Erd\u0151s\u2013R\u00e9nyi random graph <jats:italic>G<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>(<jats:italic>p<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>), where we assign independent random weights, having an exponential distribution with rate 1, to the edges. In the sparse regime, <jats:italic>i.e.<\/jats:italic>, when <jats:italic>np<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> \u2192 \u03bb &gt; 1, we find refined asymptotics both for the minimal weight of the path between uniformly chosen vertices in the giant component, as well as for the hopcount (<jats:italic>i.e.<\/jats:italic>, 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 (\u03bb log <jats:italic>n<\/jats:italic>)\/(\u03bb \u2212 1). Furthermore, we prove that the minimal weight centred by (log <jats:italic>n<\/jats:italic>)\/(\u03bb \u2212 1) converges in distribution.<\/jats:p><jats:p>We also investigate the dense regime, where <jats:italic>np<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> \u2192 \u221e. We find that although the base graph is <jats:italic>ultra-small<\/jats:italic> (meaning that graph distances between uniformly chosen vertices are <jats:italic>o<\/jats:italic>(log <jats:italic>n<\/jats:italic>)), attaching random edge weights changes the geometry of the network completely. Indeed, the hopcount <jats:italic>H<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> satisfies the universality property that whatever the value of <jats:italic>p<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>, <jats:italic>H<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>\/log <jats:italic>n<\/jats:italic> \u2192 1 in probability and, more precisely, (<jats:italic>H<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> \u2212 \u03b2<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> log <jats:italic>n<\/jats:italic>)\/<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354831100023X_char1\"\/><\/jats:private-char>, where \u03b2<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> = \u03bb<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>\/(\u03bb<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> \u2212 1), has a limiting standard normal distribution. The constant \u03b2<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> can be replaced by 1 precisely when \u03bb<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> \u226b <jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S096354831100023X_char1\"\/><\/jats:private-char>, a case that has appeared in the literature (under stronger conditions on \u03bb<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>) in [4, 13]. We also find lower bounds for the maximum, over all pairs of vertices, of the optimal weight and hopcount.<\/jats:p><jats:p>This paper continues the investigation of FPP initiated in [4] and [5]. Compared to the setting on the configuration model studied in [5], the proofs presented here are much simpler due to a direct relation between FPP on the Erd\u0151s\u2013R\u00e9nyi random graph and thinned continuous-time branching processes.<\/jats:p>","DOI":"10.1017\/s096354831100023x","type":"journal-article","created":{"date-parts":[[2011,6,20]],"date-time":"2011-06-20T04:29:52Z","timestamp":1308544192000},"page":"683-707","source":"Crossref","is-referenced-by-count":45,"title":["First Passage Percolation on the Erd\u0151s\u2013R\u00e9nyi Random Graph"],"prefix":"10.1017","volume":"20","author":[{"given":"SHANKAR","family":"BHAMIDI","sequence":"first","affiliation":[]},{"given":"REMCO","family":"VAN DER HOFSTAD","sequence":"additional","affiliation":[]},{"given":"GERARD","family":"HOOGHIEMSTRA","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2011,6,20]]},"reference":[{"key":"S096354831100023X_ref4","doi-asserted-by":"publisher","DOI":"10.1063\/1.3039876"},{"key":"S096354831100023X_ref1","unstructured":"[1] Amini H. (2011) Epidemics and percolation in random networks. PhD thesis, ENS Inria Rocquencourt."},{"key":"S096354831100023X_ref9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511755347"},{"key":"S096354831100023X_ref7","first-page":"141","article-title":"Generations and degree of relationship in supercritical Markov branching processes.","volume":"18","author":"B\u00fchler","year":"1971","journal-title":"Probab. Theory Rel. Fields"},{"key":"S096354831100023X_ref8","first-page":"1","volume-title":"An Introduction to Stein's Method","author":"Chen","year":"2005"},{"key":"S096354831100023X_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S096354831100023X_ref17","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010306"},{"key":"S096354831100023X_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-09444-0_3"},{"key":"S096354831100023X_ref12","unstructured":"[12] van der Hofstad R. (2011) Random graphs and complex networks. In preparation. www.win.tue.nl\/~rhofstad\/NotesRGCN.pdf."},{"key":"S096354831100023X_ref3","volume-title":"Branching Processes","author":"Athreya","year":"2004"},{"key":"S096354831100023X_ref13","doi-asserted-by":"publisher","DOI":"10.1017\/S026996480115206X"},{"key":"S096354831100023X_ref2","unstructured":"[2] Amini H. , Draief M. and Lelarge M. (2010) Flooding in weighted random graphs. Preprint. arxiv.org\/abs\/1011.5994"},{"key":"S096354831100023X_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316962"},{"key":"S096354831100023X_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20197"},{"key":"S096354831100023X_ref11","volume-title":"Bernoulli, 1713; Bayes, 1763; Laplace, 1813: Anniversary Volume","author":"Hammersley","year":"1965"},{"key":"S096354831100023X_ref15","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548399003892"},{"key":"S096354831100023X_ref5","doi-asserted-by":"publisher","DOI":"10.1214\/09-AAP666"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S096354831100023X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T02:33:49Z","timestamp":1556332429000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S096354831100023X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6,20]]},"references-count":17,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,9]]}},"alternative-id":["S096354831100023X"],"URL":"https:\/\/doi.org\/10.1017\/s096354831100023x","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6,20]]}}}