Central limit theorem for majority dynamics: bribing three voters suffices (Q2668498)

The theme of this paper is the analysis of majority dynamics on a random graph \(G(n,p)\), the binomial random graph on \(n\) vertices where each edge is present independently with probability \(p\). Majority dynamics is a synchronous process on the vertex set of a graph, where each vertex has two states \(red\) and \(blue\). The vertices are initially assigned there states and subsequently at each round, each vertex adopt the state of the majority of its neighbours (retaining its state in the case of a tie). The main theorem of the paper is a central limit theorem for the number of vertices which are \(red\) after the first round. This holds under certain assumptions on the difference \(\Delta\) between the number of vertices that have been assigned \(red\) and the number of vertices that have been assigned \(blues\) initially. These assumptions hold, in particular, if \(\Delta p = O(\sqrt{np(1-p})\). Now, the central limit theorem implies that the number of vertices in \(red\) after one set is away from \(n/2\) with high probability. This, in turn, has implications on the evolution of majority dynamics. The authors provide sharpener bounds on the number of rounds needed until the process reaches unanimity: if \(p = \Omega(n^{-1/2})\), at most four rounds are needed, but if \(p = \Omega (n^{-1/3})\), at most three rounds are needed, whereas if \(p\) is close to 1 then at most two rounds are needed. A second application is a bound on the difference between the probabilities that the state at unanimity is \(red\) and the state at unanimity is \(blue\). The authors prove that if \(\Delta \geq 3\) (that is, there are at least 3 more red vertices than blue ones), then this difference is more than \(1/2\).