Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs

Nikolaos Fountoulakis, Mihyun Kang, Tamás Makai

We study majority dynamics on the binomial random graph $G(n,p)$ with $p=d/n$ and $d>\lambda n^{1/2}$, for some large $\lambda >0$. In this process, each vertex has a state in $\{-1,+1\}$ a…