Projekte pro Jahr
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.
Originalsprache | englisch |
---|---|
Seiten (von - bis) | 1134-1156 |
Seitenumfang | 23 |
Fachzeitschrift | Random Structures & Algorithms |
Jahrgang | 57 |
Ausgabenummer | 4 |
DOIs | |
Publikationsstatus | Veröffentlicht - 1 Dez. 2020 |
ASJC Scopus subject areas
- Software
- Angewandte Mathematik
- Allgemeine Mathematik
- Computergrafik und computergestütztes Design
Fields of Expertise
- Information, Communication & Computing
Fingerprint
Untersuchen Sie die Forschungsthemen von „Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs“. Zusammen bilden sie einen einzigartigen Fingerprint.Projekte
- 1 Abgeschlossen
-
FWF - Cores - Zufallsgraphen: Kerne, Färbungen und Ausbreitung
1/09/18 → 30/06/22
Projekt: Forschungsprojekt