The string of diamonds is nearly tight for rumour spreading. (4th March 2020)
- Record Type:
- Journal Article
- Title:
- The string of diamonds is nearly tight for rumour spreading. (4th March 2020)
- Main Title:
- The string of diamonds is nearly tight for rumour spreading
- Authors:
- Angel, Omer
Mehrabian, Abbas
Peres, Yuval - Abstract:
- Abstarct: For a rumour spreading protocol, the spread time is defined as the first time everyone learns the rumour. We compare the synchronous push&pull rumour spreading protocol with its asynchronous variant, and show that for any n -vertex graph and any starting vertex, the ratio between their expected spread times is bounded by $O({n^{1/3}}{\log ^{2/3}}n)$ . This improves the $O(\sqrt n)$ upper bound of Giakkoupis, Nazari and Woelfel (2016). Our bound is tight up to a factor of O (log n ), as illustrated by the string of diamonds graph. We also show that if, for a pair α, β of real numbers, there exist infinitely many graphs for which the two spread times are n α and n β in expectation, then $0 \le \alpha \le 1$ and $\alpha \le \beta \le {1 \over 3} + {2 \over 3} \alpha $ ; and we show each such pair α, β is achievable.
- Is Part Of:
- Combinatorics, probability and computing. Volume 29:Number 2(2020)
- Journal:
- Combinatorics, probability and computing
- Issue:
- Volume 29:Number 2(2020)
- Issue Display:
- Volume 29, Issue 2 (2020)
- Year:
- 2020
- Volume:
- 29
- Issue:
- 2
- Issue Sort Value:
- 2020-0029-0002-0000
- Page Start:
- 190
- Page End:
- 199
- Publication Date:
- 2020-03-04
- Subjects:
- 68Q87, -- 05C81, -- 60C05, -- 68W15
Combinatorial analysis -- Periodicals
Probabilities -- Periodicals
Computer science -- Mathematics -- Periodicals
511.6 - Journal URLs:
- http://journals.cambridge.org/action/displayJournal?jid=CPC ↗
- DOI:
- 10.1017/S0963548319000385 ↗
- Languages:
- English
- ISSNs:
- 0963-5483
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library STI - ELD Digital Store
- Ingest File:
- 16818.xml