The string of diamonds is nearly tight for rumour spreading. (4th March 2020) - Angel, Omer; Mehrabian, Abbas; Peres, Yuval
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 α \le 1$ and $α \le β \le {1 \over 3} + {2 \over 3} α $ ; and we show each such pair α, β is achievable.