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

DOI10.1002/RSA.20970zbMATH Open1454.05109arXiv1910.05820OpenAlexW3097922641WikidataQ123025427 ScholiaQ123025427MaRDI QIDQ3386530FDOQ3386530

Authors: Nikolaos Fountoulakis, Mihyun Kang, Tamás Makai 

Publication date: 5 January 2021

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

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.

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

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

zbMATH Keywords

random graphsunanimitymajority dynamics

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

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

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)