Central limit theorem for majority dynamics: Bribing three voters suffices

Given a graph G and some initial labeling σ: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 Erdős–Rényi random graph, Gn,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.