Theory of Computing
-------------------
Title     : Reaching a Consensus on Random Networks: The Power of Few
Authors   : Linh Tran and Van Vu
Volume    : 19
Number    : 6
Pages     : 1-21
URL       : https://theoryofcomputing.org/articles/v019a006

Abstract
--------

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 $\epsilon$, 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 - \epsilon$. The
surprising fact here is that $c$ _does not_ depend on $n$, the
population of the community. When $p=1/2$ and $\epsilon =.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).