Reaching Consensus in Dense Erdős–Rényi Graphs

Majority dynamics on the binomial Erdős–Rényi graph G(n, p) with $p = \lambda /\sqrt n $ is studied. In this process, each vertex has a state in {0, 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. It was conjectured by Benjamini et al. and proved by Fountoulakis et al. that this process reaches unanimity with high probability in at most four rounds. We postulate an improved conjecture, according to which, majority dynamics reaches consensus with high probability in at most three rounds, and support this conjecture by computer simulations. By adding some extra randomness and allowing the underlying graph to be drawn anew in each communication round, we prove that this process reaches consensus in only three communication rounds with probability approaching 1 as n grows to infinity. We also provide a converse result, showing that three rounds are not only sufficient in this case, but also necessary, thus tightly characterizing the communication complexity of this problem for dense Erdős–Rényi graphs with independent instances.