Revised: July 20, 2022
Published: November 14, 2023
Abstract: [Plain Text Version]
A community of $n$ individuals splits into two camps, Red and Blue. The individuals are connected by a social network, which influences their colors. Every day each person changes their color according to the majority of their neighbors. Red (Blue) wins if everyone in the community becomes Red (Blue) at some point. We study this process when the underlying network is the random Erdős--Rényi graph $G(n, p)$. With a balanced initial state ($n/2$ persons in each camp), it is clear that each color wins with the same probability. Our study reveals that for any constants $p$ and $\varepsilon,ドル there is a constant $c$ such that if one camp has at least $n/2 + c$ individuals at the initial state, then it wins with probability at least 1ドル - \varepsilon$. The surprising fact here is that $c$ does not depend on $n,ドル the population of the community. When $p=1/2$ and $\varepsilon =.1,ドル one can set $c=5,ドル meaning one camp has $n/2 + 5$ members initially. In other words, it takes only 5ドル$ extra people to win an election with overwhelming odds. We also generalize the result to $p = p_n = \text{o}(1)$ in a separate paper.
-----------------
A preliminary version of this paper appeared in the Proceedings of the 24th International Conference on Randomization and Computation (RANDOM'20).