Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs
Preprint
Abstract
We study majority dynamics on the binomial random graph $G(n,p)$ with $p = d/n$ and $d > \lambda n^{1/2}$, for some large $\lambda>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.
Keywords
All Related Versions
This publication has 4 references indexed in Scilit:
- 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