Joonkyung Lee (이준경), Majority dynamics on sparse random graphs

Majority dynamics on a graph $G$ is a deterministic process such that every vertex updates its $\pm 1$-assignment according to the majority assignment on its neighbor simultaneously at each step. Benjamini, Chan, O’Donnell, Tamuz and Tan conjectured that, in the Erdős-Rényi random graph $G(n,p)$, the random initial $\pm 1$-assignment converges to a $99\mathrm{\%}$-agreement with high probability whenever $p=\omega (1/n)$.

This conjecture was first confirmed for $p\ge \lambda n^{-1/2}$ for a large constant $\lambda$ by Fountoulakis, Kang and Makai. Although this result has been reproved recently by Tran and Vu and by Berkowitz and Devlin, it was unknown whether the conjecture holds for $p<\lambda n^{-1/2}$. We break this $\mathrm{\Omega }(n^{-1/2})$-barrier by proving the conjecture for sparser random graphs $G(n,p)$, where ${\lambda }^{\prime }{n}^{-3/5}\log n\le p\le \lambda n^{-1/2}$ with a large constant ${\lambda }^{\prime }>0$.

Joint work with Debsoumya Chakraborti, Jeong Han Kim and Tuan Tran.