Premium
Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs
Author(s) -
Fountoulakis Nikolaos,
Kang Mihyun,
Makai Tamás
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20970
Subject(s) - conjecture , vertex (graph theory) , unanimity , combinatorics , mathematics , binomial (polynomial) , random graph , graph , discrete mathematics , statistics , political science , law
We study majority dynamics on the binomial random graph G ( n , p ) with p = d / n and d > λ n 1 / 2 , for some large λ > 0 . In this process, each vertex has a state in {− 1, + 1} and at each round every vertex adopts the state of the majority of its neighbors, retaining its state in the case of a tie. We show that with high probability the process reaches unanimity in at most four rounds. This confirms a conjecture of Benjamini et al.