Abstract
We study majority dynamics on the binomial random graph G(n, p) with p = d/n and , for some large . In this process, each vertex has a state in {− 1, + 1} and at each round every vertex adopts the state of the majority of its neighbors, retaining its state in the case of a tie. We show that with high probability the process reaches unanimity in at most four rounds. This confirms a conjecture of Benjamini et al.
Funding Information
  • TU Graz
  • Alan Turing Institute (EP/N5510129/1)
  • Austrian Science Fund (I3747, W1230III)
  • EPSRC (EP/S016694/1)
  • ARC (DP190100977)