{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T07:41:27Z","timestamp":1648539687534},"reference-count":11,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T00:00:00Z","timestamp":1572825600000},"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":[[2020,3]]},"abstract":"<jats:title>Abstarct<\/jats:title><jats:p>For a rumour spreading protocol, the spread time is defined as the first time everyone learns the rumour. We compare the synchronous push&amp;pull rumour spreading protocol with its asynchronous variant, and show that for any <jats:italic>n<\/jats:italic>-vertex graph and any starting vertex, the ratio between their expected spread times is bounded by <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000385_inline1.png\" \/><jats:tex-math>$O({n^{1\/3}}{\\log ^{2\/3}}n)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. This improves the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000385_inline2.png\" \/><jats:tex-math>$O(\\sqrt n)$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> upper bound of Giakkoupis, Nazari and Woelfel (2016). Our bound is tight up to a factor of <jats:italic>O<\/jats:italic>(log <jats:italic>n<\/jats:italic>), as illustrated by the string of diamonds graph. We also show that if, for a pair <jats:italic>\u03b1<\/jats:italic>, <jats:italic>\u03b2<\/jats:italic> of real numbers, there exist infinitely many graphs for which the two spread times are <jats:italic>n<\/jats:italic><jats:sup><jats:italic>\u03b1<\/jats:italic><\/jats:sup> and <jats:italic>n<\/jats:italic><jats:sup><jats:italic>\u03b2<\/jats:italic><\/jats:sup> in expectation, then <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000385_inline3.png\" \/><jats:tex-math>$0 \\le \\alpha \\le 1$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548319000385_inline4.png\" \/><jats:tex-math>$\\alpha \\le \\beta \\le {1 \\over 3} + {2 \\over 3} \\alpha $<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>; and we show each such pair <jats:italic>\u03b1<\/jats:italic>, <jats:italic>\u03b2<\/jats:italic> is achievable.<\/jats:p>","DOI":"10.1017\/s0963548319000385","type":"journal-article","created":{"date-parts":[[2019,11,4]],"date-time":"2019-11-04T07:55:46Z","timestamp":1572854146000},"page":"190-199","source":"Crossref","is-referenced-by-count":0,"title":["The string of diamonds is nearly tight for rumour spreading"],"prefix":"10.1017","volume":"29","author":[{"given":"Omer","family":"Angel","sequence":"first","affiliation":[]},{"given":"Abbas","family":"Mehrabian","sequence":"additional","affiliation":[]},{"given":"Yuval","family":"Peres","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2019,11,4]]},"reference":[{"key":"S0963548319000385_ref11","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100077288"},{"key":"S0963548319000385_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933117"},{"key":"S0963548319000385_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-46693-9_21"},{"key":"S0963548319000385_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34862-4_12"},{"key":"S0963548319000385_ref4","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"S0963548319000385_ref1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1033113"},{"key":"S0963548319000385_ref3","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874516"},{"key":"S0963548319000385_ref10","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892324"},{"key":"S0963548319000385_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010406"},{"key":"S0963548319000385_ref2","volume-title":"Series","author":"Auffinger","year":"2017"},{"key":"S0963548319000385_ref9","first-page":"61","volume-title":"First-Passage Percolation, Subadditive Processes, Stochastic Networks, and Generalized Renewal Theory","author":"Hammersley","year":"1965"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548319000385","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,25]],"date-time":"2020-03-25T08:15:15Z","timestamp":1585124115000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548319000385\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11,4]]},"references-count":11,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["S0963548319000385"],"URL":"https:\/\/doi.org\/10.1017\/s0963548319000385","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,11,4]]}}}