Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs
Open Access
- 13 October 2020
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 57 (4) , 1134-1156
Abstract
We study majority dynamics on the binomial random graph G(n, p) with p = d/n and , for some large . 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.Keywords
All Related Versions
Funding Information
- TU Graz
- Alan Turing Institute (EP/N5510129/1)
- Austrian Science Fund (I3747, W1230III)
- EPSRC (EP/S016694/1)
- ARC (DP190100977)
This publication has 9 references indexed in Scilit:
- Majority Model on Random Regular Graphs2018
- Color War: Cellular Automata with Majority-Rule2017
- Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphsStochastic Processes and their Applications, 2016
- Global majority consensus by local majority polling on graphs of a given degree sequenceDiscrete Applied Mathematics, 2015
- Majority dynamics and aggregation of information in social networksAutonomous Agents and Multi-Agent Systems, 2013
- Periodic behaviour of generalized threshold functionsDiscrete Mathematics, 1980
- Threshold Models of Collective BehaviorAmerican Journal of Sociology, 1978
- Sums of Independent Random Variables1975
- Mathematical GamesScientific American, 1970