Revised: July 20, 2022

Published: November 14, 2023

**Keywords:**random graphs, Erdös-Rényi model, majority dynamics, consensus

**Categories:**random graphs, Erdös-Rényi model, majority dynamics, consensus, RANDOM, APPROX-RANDOM 2020 special issue

**ACM Classification:**F.2.0

**AMS Classification:**68Q25, 68W25

**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).