Central limit theorem for majority dynamics: bribing three voters suffices

DOI10.1016/j.spa.2022.01.010zbMath1489.60037arXiv2010.08172OpenAlexW4226049447WikidataQ113863846 ScholiaQ113863846MaRDI QIDQ2668498

Pat Devlin, Ross Berkowitz

Publication date: 7 March 2022

Published in: Stochastic Processes and their Applications (Search for Journal in Brave)

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

zbMATH Keywords

Fourier analysiscentral limit theoremrandom graphmajority dynamics

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (2)

Majority dynamics on sparse random graphs ⋮ Majority vote in social networks

Cites Work

• Global majority consensus by local majority polling on graphs of a given degree sequence
• Majority dynamics on trees and the dynamic cavity method
• Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs
• Periodic behaviour of generalized threshold functions
• Convergence in energy-lowering (disordered) stochastic spin systems
• The majority action on infinite graphs: Strings and puppets
• Majority model on random regular graphs
• Opinion forming in Erdős-Rényi random graph and expanders
• Majority dynamics and the retention of information
• Dynamic monopolies in two-way bootstrap percolation
• Fixation to Consensus on Tree-related Graphs
• Resolution of a conjecture on majority dynamics: Rapid stabilization in dense random graphs
• Gossip Algorithms
• Bootstrap percolation on the random regular graph
• Learning from Neighbours
• Analysis of Boolean Functions
• Color War: Cellular Automata with Majority-Rule

This page was built for publication: Central limit theorem for majority dynamics: bribing three voters suffices