Projects per year
Abstract
We study majority dynamics on the binomial random graph G(n, p) with p = d/n and (Formula presented.), for some large (Formula presented.). 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.
Original language | English |
---|---|
Pages (from-to) | 1134-1156 |
Number of pages | 23 |
Journal | Random Structures & Algorithms |
Volume | 57 |
Issue number | 4 |
DOIs | |
Publication status | Published - 1 Dec 2020 |
Keywords
- majority dynamics
- random graphs
- unanimity
ASJC Scopus subject areas
- Software
- Applied Mathematics
- Mathematics(all)
- Computer Graphics and Computer-Aided Design
Fields of Expertise
- Information, Communication & Computing
Fingerprint
Dive into the research topics of 'Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs'. Together they form a unique fingerprint.Projects
- 1 Finished
-
FWF - Cores - Random Graphs: Cores, Colourings and Contagion
1/09/18 → 30/06/22
Project: Research project