Discrete incremental voting on expanders

DOI10.1016/J.DISC.2025.114708MaRDI QIDQ6930275zbMATH OpenFDO

Authors Colin Cooper, Tomasz Radzik, Takeharu Shiraga

Publication date 16 September 2025

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DISC.2025.114708

zbMATH Keywords

random distributed processrandom walkrandomized pull voting

Mathematics Subject Classification ID

Expander graphs (05C48) Random walks on graphs (05C81) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Processes in random environments (60K37)

Cites work

• Distributed probabilistic polling and applications to proportionate agreement
• Fast consensus for voting on general expander graphs
• Global majority consensus by local majority polling on graphs of a given degree sequence
• scientific article; zbMATH DE number 1405692 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Nearly-tight analysis for 2-choice and 3-majority consensus dynamics
• On the Laplacian Eigenvalues of G_n,p
• Phase transitions of Best‐of‐two and Best‐of‐three on stochastic block models
• Plurality consensus in the gossip model
• Size biased couplings and the spectral gap for random regular graphs
• Stabilizing Consensus with Many Opinions
• The Power of Two Choices in Distributed Voting
• The spectral gap of dense random regular graphs

This page was built for publication: Discrete incremental voting on expanders

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