{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T04:31:54Z","timestamp":1648528314906},"reference-count":21,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,6,13]],"date-time":"2014-06-13T00:00:00Z","timestamp":1402617600000},"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":[[2014,7]]},"abstract":"<jats:p>The <jats:italic>spread<\/jats:italic> of a connected graph <jats:italic>G<\/jats:italic> was introduced by Alon, Boppana and Spencer [1], and measures how tightly connected the graph is. It is defined as the maximum over all Lipschitz functions <jats:italic>f<\/jats:italic> on <jats:italic>V(G)<\/jats:italic> of the variance of <jats:italic>f(X)<\/jats:italic> when <jats:italic>X<\/jats:italic> is uniformly distributed on <jats:italic>V(G)<\/jats:italic>. We investigate the spread for certain models of sparse random graph, in particular for random regular graphs <jats:italic>G(n,d)<\/jats:italic>, for Erd\u0151s\u2013R\u00e9nyi random graphs <jats:italic>G<jats:sub>n,p<\/jats:sub><\/jats:italic> in the supercritical range <jats:italic>p&gt;1\/n<\/jats:italic>, and for a \u2018small world\u2019 model. For supercritical <jats:italic>G<jats:sub>n,p<\/jats:sub><\/jats:italic>, we show that if <jats:italic>p=c\/n<\/jats:italic> with <jats:italic>c<\/jats:italic>&gt;1 fixed, then with high probability the spread of the giant component is bounded, and we prove corresponding statements for other models of random graphs, including a model with random edge lengths. We also give lower bounds on the spread for the barely supercritical case when <jats:italic>p=(1+o(1))\/n<\/jats:italic>. Further, we show that for <jats:italic>d<\/jats:italic> large, with high probability the spread of <jats:italic>G(n,d)<\/jats:italic> becomes arbitrarily close to that of the complete graph <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548314000248_inline1\" \/><jats:tex-math>$\\mathsf{K}_n$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1017\/s0963548314000248","type":"journal-article","created":{"date-parts":[[2014,6,13]],"date-time":"2014-06-13T14:50:07Z","timestamp":1402671007000},"page":"477-504","source":"Crossref","is-referenced-by-count":0,"title":["On the Spread of Random Graphs"],"prefix":"10.1017","volume":"23","author":[{"given":"LOUIGI","family":"ADDARIO-BERRY","sequence":"first","affiliation":[]},{"given":"SVANTE","family":"JANSON","sequence":"additional","affiliation":[]},{"given":"COLIN","family":"McDIARMID","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,6,13]]},"reference":[{"key":"S0963548314000248_ref21","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"S0963548314000248_ref18","volume-title":"Random Forests","author":"Pavlov","year":"1996"},{"key":"S0963548314000248_ref7","volume-title":"Random Graph Dynamics","author":"Durrett","year":"2010"},{"key":"S0963548314000248_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(99)00757-4"},{"key":"S0963548314000248_ref8","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20147"},{"key":"S0963548314000248_ref6","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M"},{"key":"S0963548314000248_ref1","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050062"},{"key":"S0963548314000248_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20539"},{"key":"S0963548314000248_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(80)90172-7"},{"key":"S0963548314000248_ref11","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176346079"},{"key":"S0963548314000248_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240040303"},{"key":"S0963548314000248_ref4","volume-title":"Cambridge Studies in Advanced Mathematics","author":"Bollob\u00e1s","year":"2001"},{"key":"S0963548314000248_ref13","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010305"},{"key":"S0963548314000248_ref12","volume-title":"Random Mappings","author":"Kolchin","year":"1986"},{"key":"S0963548314000248_ref10","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548314000248_ref19","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000325"},{"key":"S0963548314000248_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02773835"},{"key":"S0963548314000248_ref15","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020405"},{"key":"S0963548314000248_ref17","first-page":"523","article-title":"The asymptotic distribution of maximum tree size in a random forest (in Russian)","volume":"22","author":"Pavlov","year":"1977","journal-title":"Teor. Verojatnost. i Primenen."},{"key":"S0963548314000248_ref5","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000301"},{"key":"S0963548314000248_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(91)90162-U"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548314000248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,22]],"date-time":"2019-04-22T03:13:47Z","timestamp":1555902827000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548314000248\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,6,13]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["S0963548314000248"],"URL":"https:\/\/doi.org\/10.1017\/s0963548314000248","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,6,13]]}}}