# Rumor Spreading and Vertex Expansion

## George Giakkoupis and Thomas Sauerwald

Abstract:
We study the relation between the rate at which rumors spread throughout a graph and the vertex expansion of the graph. We consider the standard rumor spreading protocol where every node chooses a random neighbor in each round and the two nodes exchange the rumors they know. For any n-node graph with vertex expansion $\alpha$, we show that this protocol spreads a rumor from a single node to all other nodes in $O(\alpha^{-1} \log
^2 n \sqrt{\log n})$
rounds with high probability. Further, we construct graphs for which $\Omega(\alpha^{-1} \log^2 n)$ rounds are needed. Our results complement a long series of works that relate rumor spreading to edge-based notions of expansion, resolving one of the most natural questions on the connection between rumor spreading and expansion.

Guest: George Giakkoupis
Host: Chen Avin