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

DOI10.1002/rsa.20970zbMath1454.05109arXiv1910.05820OpenAlexW3097922641WikidataQ123025427 ScholiaQ123025427MaRDI QIDQ3386530

Tamás Makai, Mihyun Kang, Nikolaos Fountoulakis

Publication date: 5 January 2021

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

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)

Related Items (8)

Degree sequences of sufficiently dense random uniform hypergraphs ⋮ Central limit theorem for majority dynamics: bribing three voters suffices ⋮ Majority dynamics on sparse random graphs ⋮ Majority vote in social networks ⋮ Unnamed Item ⋮ A note on the majority dynamics in inhomogeneous random graphs ⋮ Best response dynamics on random graphs ⋮ Majority dynamics and the median process: connections, convergence and some new conjectures

Cites Work

• Unnamed Item
• 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
• Periodic behaviour of generalized threshold functions
• Majority model on random regular graphs
• Opinion Forming in Erdös-Rényi Random Graph and Expanders
• Color War: Cellular Automata with Majority-Rule

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