Central limit theorem for majority dynamics: Bribing three voters suffices

Given a graph G and some initial labeling sigma : V(G) ->{Red, Blue} of its vertices, the majority dynamics model is the deterministic process where at each stage, every vertex simultaneously replaces its label with the majority label among its neighbors (remaining unchanged in the case of a tie). We prove for a wide range of parameters that if an initial assignment is fixed and we independently sample an Erdos-Renyi random graph, G(n, p), then after one step of majority dynamics, the number of vertices of each label follows a central limit law. As a corollary, we provide a strengthening of a theorem of Benjamini, Chan, O'Donnell, Tamuz, and Tan about the number of steps required for the process to reach unanimity when the initial assignment is also chosen randomly. Moreover, suppose there are initially three more red vertices than blue. In this setting, we prove that if we independently sample the graph G(n,1/2), then with probability at least 51%, the majority dynamics process will converge to every vertex being red. This improves a result of Tran and Vu who addressed the case that the initial lead is at least 10. (c) 2022 Elsevier B.V. All rights reserved.