Projects per year
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 language | English |
---|---|
Pages (from-to) | 1134-1156 |
Journal | Random Structures and Algorithms |
Volume | 57 |
Issue number | 4 |
DOIs | |
Publication status | Published - 10 Jul 2020 |
Keywords
- majority dynamics
- random graphs
- unanimity
ASJC Scopus subject areas
- General Mathematics
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.Projects
- 1 Finished