Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs. Issue 4 (13th October 2020)

• Record Type: Journal Article
• Authors: Fountoulakis, Nikolaos; Kang, Mihyun; Makai, Tamás
• Is Part Of: Random structures & algorithms. Volume 57:Issue 4(2020)
• Page Start: 1134
• Page End: 1156
• Publication Date: 2020-10-13
• Subjects: majority dynamics -- random graphs -- unanimity; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20970
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : 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.