Majority dynamics on random graphs: The multiple states case

Jordan Chellig and Nikolaos Fountoulakis

Stochastic Processes and their Applications, 2025, vol. 189, issue C

Abstract: We study the evolution of majority dynamics with more than two states on the binomial random graph G(n,p). In this process, each vertex has a state in {1,…,k}, with k≥3, and at each round every vertex adopts state i if it has more neighbours in state i than in any other state. Ties are resolved randomly. We show that with high probability the process reaches unanimity in at most three rounds, if np≫n2/3.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414925001231
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:189:y:2025:i:c:s0304414925001231

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2025.104682

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().