Majority dynamics on random graphs: the multiple states case

Jordan CHELLIG; Nikolaos Fountoulakis

doi:10.1016/j.spa.2025.104682

Majority dynamics on random graphs: the multiple states case

Jordan CHELLIG
, Nikolaos Fountoulakis^*

^*Corresponding author for this work

Mathematics

Research output: Contribution to journal › Article › peer-review

44 Downloads (Pure)

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 ≥ 2, 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>> n^2/3.

Original language	English
Article number	104682
Number of pages	40
Journal	Stochastic Processes and their Applications
Volume	189
Early online date	27 May 2025
DOIs	https://doi.org/10.1016/j.spa.2025.104682
Publication status	Published - Nov 2025

Keywords

Random graphs
majority dynamics
unanimity

Access to Document

10.1016/j.spa.2025.104682Licence: Creative Commons: Attribution (CC BY)

ChelligJ2025MajorityFinal published version, 1.07 MBLicence: Creative Commons: Attribution (CC BY)

Cite this

@article{aabcf209e4e64295887a96916cd01a17,

title = "Majority dynamics on random graphs: the multiple states case",

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 ≥ 2, 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.",

keywords = "Random graphs, majority dynamics, unanimity",

author = "Jordan CHELLIG and Nikolaos Fountoulakis",

year = "2025",

month = nov,

doi = "10.1016/j.spa.2025.104682",

language = "English",

volume = "189",

journal = "Stochastic Processes and their Applications",

issn = "0304-4149",

publisher = "Elsevier",

}

TY - JOUR

T1 - Majority dynamics on random graphs

T2 - the multiple states case

AU - CHELLIG, Jordan

AU - Fountoulakis, Nikolaos

PY - 2025/11

Y1 - 2025/11

N2 - 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 ≥ 2, 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.

AB - 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 ≥ 2, 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.

KW - Random graphs

KW - majority dynamics

KW - unanimity

U2 - 10.1016/j.spa.2025.104682

DO - 10.1016/j.spa.2025.104682

M3 - Article

SN - 0304-4149

VL - 189

JO - Stochastic Processes and their Applications

JF - Stochastic Processes and their Applications

M1 - 104682

ER -

Majority dynamics on random graphs: the multiple states case

Abstract

Keywords

Access to Document

Fingerprint

Cite this