The string of diamonds is nearly tight for rumour spreading. (4th March 2020)

• Record Type: Journal Article
• Authors: Angel, Omer; Mehrabian, Abbas; Peres, Yuval
• Is Part Of: Combinatorics, probability and computing. Volume 29:Number 2(2020)
• 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
• DOI: 10.1017/S0963548319000385
• Languages: English
• ISSNs: 0963-5483

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.