Benjamini et al.'s conjecture on consensus in sparse random-graph majority dynamics

Let $G(n,p)$ be a random graph, let $P_t$ and $N_t$ denote the sets of vertices playing the two strategies at time $t$, and let $d$ be the parameter in the condition $p\geq d/n$. Consider the majority dynamics process with a uniformly chosen initial state. With high probability over the choice of the random graph and the initial state, the following holds. Benjamini et al.'s conjecture. If $d\gg 1$, then, for every $\varepsilon>0$ and all sufficiently large $n$,

$$\lim_{t\rightarrow\infty}\left|\lvert P_{2t}\rvert-\lvert N_{2t}\rvert\right|\in[(1-\varepsilon)n,n].$$

If $d$ is bounded, then, for every $\varepsilon>0$ and all sufficiently large $n$,

$$\lim_{t\rightarrow\infty}\left|\lvert P_{2t}\rvert-\lvert N_{2t}\rvert\right|\in[(1-\varepsilon/2)n,(1+\varepsilon/2)n].$$

The conjecture concerns the poorly understood evolution of majority dynamics on random graphs in the sparse regime $p=o(n^{-1/2})$, beyond the regimes treated by the paper; apart from eventual periodicity, little is known about the dynamics.