Majority dynamics on sparse random graphs
Abstract
Consider a simple undirected graph G on N vertices, with each vertex holding an opinion from one of two options. Starting from the initial opinions on day 1, we run majority dynamics: on each subsequent day, all vertices simultaneously adopt the majority opinion among their neighbors, retaining their current opinion in case of a tie. A well-studied conjecture of Benjamini, Chan, O'Donnell, Tamuz, and Tan states that if G is drawn from the random binomial model 𝔾(N,p), and if the starting opinions are chosen uniformly at random, then as long as pN → ∞ the network will converge to 99% consensus with high probability. We confirm this conjecture as long as pN ≥ Nε for any fixed ε > 0, showing that full unanimity is reached with high probability in O(1/ε) days. This result improves on a line of results by Fountoulakis, Kang, and Makai, who achieve ε = 1/2; Chakraborti, Kim, Lee, and Tran, who achieve ε = 2/5; and Jaffe, who achieves ε = 1/3. The proof technique involves iteratively revealing the "opinion histories" for each vertex through time, keeping track of the degrees between every vertex and each of 2k opinion history classes on day k. Our analysis of this process requires intricate estimates for degree-constrained random graph models using graph enumeration tools from the work of McKay and Wormald as well as Canfield, Greenhill, and McKay, and their extensions by Liebenau and Wormald. In doing so, we connect the discrete dynamics to a deterministic idealized process, whose leading-order behavior is described by conditional Gaussian probabilities and expectations.
Related
- Majority Dynamics on Resampled Sparse Erdős--Rényi Graphs: Gaussian Winner Selection in Collaborative Agent Networks
- Optimal path decompositions of sparse random graphs
- Coloring sparse random Cayley graphs
- A first order phase transition for lower tails in sparse random graphs
- The lower tail of triangle counts in sparse random graphs
BibTeX
@misc{goel2026majority,
title = {{Majority dynamics on sparse random graphs}},
author = {Gopal Goel and Ashwin Sah},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.14957},
eprint = {2609.14957},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.14957},
}
RIS
TY - UNPB
TI - Majority dynamics on sparse random graphs
AU - Gopal Goel
AU - Ashwin Sah
PY - 2026
DA - 2026/09/14
PB - arXiv
DO - 10.48550/arxiv.2609.14957
UR - https://arxiv.org/abs/2609.14957
AB - Consider a simple undirected graph G on N vertices, with each vertex holding an opinion from one of two options. Starting from the initial opinions on day 1, we run majority dynamics: on each subsequent day, all vertices simultaneously adopt the majority opinion among their neighbors, retaining their current opinion in case of a tie. A well-studied conjecture of Benjamini, Chan, O'Donnell, Tamuz, and Tan states that if G is drawn from the random binomial model 𝔾(N,p), and if the starting opinions are chosen uniformly at random, then as long as pN → ∞ the network will converge to 99% consensus with high probability. We confirm this conjecture as long as pN ≥ N^ε for any fixed ε > 0, showing that full unanimity is reached with high probability in O(1/ε) days. This result improves on a line of results by Fountoulakis, Kang, and Makai, who achieve ε = 1/2; Chakraborti, Kim, Lee, and Tran, who achieve ε = 2/5; and Jaffe, who achieves ε = 1/3. The proof technique involves iteratively revealing the "opinion histories" for each vertex through time, keeping track of the degrees between every vertex and each of 2^k opinion history classes on day k. Our analysis of this process requires intricate estimates for degree-constrained random graph models using graph enumeration tools from the work of McKay and Wormald as well as Canfield, Greenhill, and McKay, and their extensions by Liebenau and Wormald. In doing so, we connect the discrete dynamics to a deterministic idealized process, whose leading-order behavior is described by conditional Gaussian probabilities and expectations.
ER -