Metraipolis › archive › dc_04d4e1ed2ada

Majority dynamics on sparse random graphs — arXiv:2609.14957

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.14957
License (as archived): CC0-1.0
Archived: 2026-10-16T01:18:50.810Z
SHA-256 of the archived text: 220466e477aca68f9d9d4a65fda90a8747b4d760f96f7618129453d93fddc86e
Stable URL of this page: https://metraipolis.com/documento/dc_04d4e1ed2ada

How to cite

Majority dynamics on sparse random graphs — arXiv:2609.14957 — arXiv (en), https://arxiv.org/abs/2609.14957 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_04d4e1ed2ada (Metraipolis archive dc_04d4e1ed2ada, sha256 220466e477aca68f9d9d4a65fda90a8747b4d760f96f7618129453d93fddc86e)

BibTeX

@misc{dc04d4e1ed2ada,
  title = {Majority dynamics on sparse random graphs — arXiv:2609.14957},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.14957},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_04d4e1ed2ada; sha256 220466e477aca68f9d9d4a65fda90a8747b4d760f96f7618129453d93fddc86e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.14957. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\mathbb{G}(N,p)$, and if the starting opinions are chosen uniformly at random, then as long as $pN \to \infty$ the network will converge to 99% consensus with high probability. We confirm this conjecture as long as $pN \ge N^{\varepsilon}$ for any fixed $\varepsilon > 0$, showing that full unanimity is reached with high probability in $O(1/\varepsilon)$ days. This result improves on a line of results by Fountoulakis, Kang, and Makai, who achieve $\varepsilon = 1/2$; Chakraborti, Kim, Lee, and Tran, who achieve $\varepsilon = 2/5$; and Jaffe, who achieves $\varepsilon = 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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in math.PR).
Categorie arXiv: Probability (math.PR) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.14957 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T00:31:28.431Z dalla pagina https://arxiv.org/catchup/math.PR/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).