Majority dynamics on a graph G is a deterministic process such that every vertex updates its ±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˝os–R´enyi random graph G(n, p), the random initial ±1-assignment converges to a 99%-agreement with high probability whenever p >> 1/n.
This conjecture was first confirmed for p ≥ λn−1/2 for a large constant λ 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 < λn−1/2 .
We break this Ω(n −1/2 )-barrier by proving the conjecture for sparser random graphs G(n, p) with
λn − 2/3 log2/3 n ≤ p ≤ λn − 1/2
for a large constant λ > 0. Joint work with D. Chakraborti, J. Lee, & T. Tran, and with L. Tran.