Publications
Home
Schools
Computational Sciences
Publications
- Title
- Majority dynamics on sparse random graphs
- KIAS Author
- Kim, Jeong Han
- Journal
- RANDOM STRUCTURES & ALGORITHMS, 2023
- Archive
-
- Abstract
- 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 Erdos-Renyi random graph G(n,p), the random initial +/- 1-assignment converges to a 99%-agreement with high probability whenever p = w(1/n). This conjecture was first confirmed for p > lambda n(-1/2) for a large constant A 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 omega(n(-1/2))-barrier by proving the conjecture for sparser random graphs G(n,p), where lambda ' n(-3/5) log n < p < lambda n(-1/2) with a large constant A ' > 0.