Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs

Nikolaos Fountoulakis, Mihyun Kang, Tamas Makai

Research output: Contribution to journalArticlepeer-review

Abstract

We study majority dynamics on the binomial random graph G(n,p) with p = d/n and d > c n^{1/2}, for some large c>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 neighbours, 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, Chan, O'Donnel, Tamuz and Tan.
Original languageEnglish
JournalRandom Structures and Algorithms
DOIs
Publication statusPublished - 10 Jul 2020

Keywords

  • majority dynamics
  • random graphs
  • unanimity

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs'. Together they form a unique fingerprint.

Cite this