Resolution of a conjecture on majority dynamics: rapid stabilization in dense random graphs

DOI10.1002/RSA.20970MaRDI QIDQ3386530zbMATH OpenOpenAlexWikidataFDO

Authors Nikolaos Fountoulakis, Mihyun Kang, Tamás Makai

Publication date 5 January 2021

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.05820

zbMATH Keywords

random graphsunanimitymajority dynamics

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)

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.

Recommendations

• Majority dynamics on sparse random graphs
• Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
• Central limit theorem for majority dynamics: bribing three voters suffices
• Majority dynamics and the median process: connections, convergence and some new conjectures
• A note on the majority dynamics in inhomogeneous random graphs

Cites work

• scientific article; zbMATH DE number 3504208 (Why is no real title available?)
• Color War: Cellular Automata with Majority-Rule
• Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
• Global majority consensus by local majority polling on graphs of a given degree sequence
• Majority model on random regular graphs
• Opinion Forming in Erdös-Rényi Random Graph and Expanders
• Periodic behaviour of generalized threshold functions

Cited in

(12)

• Central limit theorem for majority dynamics: bribing three voters suffices
• Majority model on random regular graphs
• Degree sequences of sufficiently dense random uniform hypergraphs
• A note on the majority dynamics in inhomogeneous random graphs
• Majority dynamics on sparse random graphs
• Best response dynamics on random graphs
• Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
• scientific article; zbMATH DE number 7758322 (Why is no real title available?)
• Majority vote in social networks
• Majority dynamics and the median process: connections, convergence and some new conjectures
• Fixation to consensus on tree-related graphs
• Brief announcement: Phase transitions of the \(k\)-majority dynamics in a biased communication model

This page was built for publication: Resolution of a conjecture on majority dynamics: rapid stabilization in dense random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386530)