{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,5]],"date-time":"2023-10-05T09:48:40Z","timestamp":1696499320268},"reference-count":23,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2010,10,5]],"date-time":"2010-10-05T00:00:00Z","timestamp":1286236800000},"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":[[2010,11]]},"abstract":"<jats:p>We study the diameter of<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000301_char1\" \/><\/jats:private-char><jats:sub>1<\/jats:sub>, the largest component of the Erd\u0151s\u2013R\u00e9nyi random graph<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000301_char2\" \/><\/jats:private-char>(<jats:italic>n<\/jats:italic>,<jats:italic>p<\/jats:italic>) in the emerging supercritical phase,<jats:italic>i.e.<\/jats:italic>, for<jats:italic>p<\/jats:italic>=<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000301_inline1\"><jats:alt-text>$\\frac{1+\\epsilon}n$<\/jats:alt-text><\/jats:inline-graphic>where \u03b5<jats:sup>3<\/jats:sup><jats:italic>n<\/jats:italic>\u2192 \u221e and \u03b5 =<jats:italic>o<\/jats:italic>(1). This parameter was extensively studied for fixed \u03b5 &gt; 0, yet results for \u03b5 =<jats:italic>o<\/jats:italic>(1) outside the critical window were only obtained very recently. Prior to this work, Riordan and Wormald gave precise estimates on the diameter; however, these did not cover the entire supercritical regime (namely, when \u03b5<jats:sup>3<\/jats:sup><jats:italic>n<\/jats:italic>\u2192 \u221e arbitrarily slowly). \u0141uczak and Seierstad estimated its order throughout this regime, yet their upper and lower bounds differed by a factor of<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000301_inline2\"><jats:alt-text>$\\frac{1000}7$<\/jats:alt-text><\/jats:inline-graphic>.<\/jats:p><jats:p>We show that throughout the emerging supercritical phase,<jats:italic>i.e.<\/jats:italic>, for any \u03b5 =<jats:italic>o<\/jats:italic>(1) with \u03b5<jats:sup>3<\/jats:sup><jats:italic>n<\/jats:italic>\u2192 \u221e, the diameter of<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000301_char1\" \/><\/jats:private-char><jats:sub>1<\/jats:sub>is with high probability asymptotic to<jats:italic>D<\/jats:italic>(\u03b5,<jats:italic>n<\/jats:italic>) = (3\/\u03b5)log(\u03b5<jats:sup>3<\/jats:sup><jats:italic>n<\/jats:italic>). This constitutes the first proof of the asymptotics of the diameter valid throughout this phase. The proof relies on a recent structure result for the supercritical giant component, which reduces the problem of estimating distances between its vertices to the study of passage times in first-passage percolation. The main advantage of our method is its flexibility. It also implies that in the emerging supercritical phase the diameter of the 2-core of<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000301_char1\" \/><\/jats:private-char><jats:sub>1<\/jats:sub>is w.h.p. asymptotic to<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000301_inline3\"><jats:alt-text>$\\frac23 D(\\epsilon,n)$<\/jats:alt-text><\/jats:inline-graphic>, and the maximal distance in<jats:private-char><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000301_char1\" \/><\/jats:private-char><jats:sub>1<\/jats:sub>between any pair of kernel vertices is w.h.p. asymptotic to<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548310000301_inline4\"><jats:alt-text>$\\frac{5}9D(\\epsilon,n)$<\/jats:alt-text><\/jats:inline-graphic>.<\/jats:p>","DOI":"10.1017\/s0963548310000301","type":"journal-article","created":{"date-parts":[[2010,10,5]],"date-time":"2010-10-05T14:34:30Z","timestamp":1286289270000},"page":"729-751","source":"Crossref","is-referenced-by-count":20,"title":["Diameters in Supercritical Random Graphs Via First Passage Percolation"],"prefix":"10.1017","volume":"19","author":[{"given":"JIAN","family":"DING","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JEONG HAN","family":"KIM","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"EYAL","family":"LUBETZKY","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"YUVAL","family":"PERES","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2010,10,5]]},"reference":[{"key":"S0963548310000301_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/9780470277331"},{"key":"S0963548310000301_ref7","doi-asserted-by":"publisher","DOI":"10.2307\/1999405"},{"key":"S0963548310000301_ref5","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80030-8"},{"key":"S0963548310000301_ref23","first-page":"239","volume-title":"London Mathematical Society Lecture Notes","author":"Wormald","year":"1999"},{"key":"S0963548310000301_ref18","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176989540"},{"key":"S0963548310000301_ref9","doi-asserted-by":"publisher","DOI":"10.1006\/aama.2001.0720"},{"key":"S0963548310000301_ref4","doi-asserted-by":"publisher","DOI":"10.1214\/09-AAP666"},{"key":"S0963548310000301_ref19","doi-asserted-by":"publisher","DOI":"10.1214\/07-AOP358"},{"key":"S0963548310000301_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548310000301_ref3","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/453\/08795"},{"key":"S0963548310000301_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20168"},{"key":"S0963548310000301_ref20","first-page":"193","volume-title":"Lectures on Probability Theory and Statistics","author":"Peres","year":"1997"},{"key":"S0963548310000301_ref12","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20197"},{"key":"S0963548310000301_ref1","unstructured":"[1] Addario-Berry L. , Broutin N. and Goldschmidt C. (2009) The continuum limit of critical random graphs. Available at: http:\/\/arxiv.org\/abs\/0903.4730."},{"key":"S0963548310000301_ref6","volume-title":"Cambridge Studies in Advanced Mathematics","author":"Bollob\u00e1s","year":"2001"},{"key":"S0963548310000301_ref10","unstructured":"[10] Ding J. , Kim J. H. , Lubetzky E. and Peres Y. Anatomy of a young giant component in the random graph. Random Struct. Alg., in press. Available at: http:\/\/arxiv.org\/abs\/0906.1839."},{"key":"S0963548310000301_ref11","doi-asserted-by":"crossref","first-page":"290","DOI":"10.5486\/PMD.1959.6.3-4.12","article-title":"On random graphs I.","volume":"6","author":"Erd\u0151s","year":"1959","journal-title":"Publ. Math. Debrecen"},{"key":"S0963548310000301_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0074919"},{"key":"S0963548310000301_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010305"},{"key":"S0963548310000301_ref17","unstructured":"[17] \u0141uczak T. and Seierstad T. G. The diameter behavior in the random graph process. Preprint."},{"key":"S0963548310000301_ref21","unstructured":"[21] Riordan O. and Wormald N. C. (2008) The diameter of sparse random graphs. Preprint, available at: http:\/\/arxiv.org\/abs\/0808.4067v1."},{"key":"S0963548310000301_ref22","unstructured":"[22] Riordan O. and Wormald N. C. (2009) The diameter of sparse random graphs. To appear, available at: http:\/\/arxiv.org\/abs\/0808.4067v2."},{"key":"S0963548310000301_ref16","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<485::AID-RSA16>3.0.CO;2-Y"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548310000301","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,3]],"date-time":"2023-06-03T16:34:36Z","timestamp":1685810076000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548310000301\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,10,5]]},"references-count":23,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["S0963548310000301"],"URL":"https:\/\/doi.org\/10.1017\/s0963548310000301","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,10,5]]}}}