Majority dynamics on random graphs: the multiple states case
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908354780069888 |
|---|---|
| author | Chellig, Jordan Fountoulakis, Nikolaos |
| author_facet | Chellig, Jordan Fountoulakis, Nikolaos |
| contents | 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,\ldots, k\}$, with $k\geq 3$, and at each round every vertex adopts state $i$ if it has more neighbours in state $i$ that 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\gg n^{2/3}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_09078 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Majority dynamics on random graphs: the multiple states case Chellig, Jordan Fountoulakis, Nikolaos Probability Combinatorics 05C80 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,\ldots, k\}$, with $k\geq 3$, and at each round every vertex adopts state $i$ if it has more neighbours in state $i$ that 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\gg n^{2/3}$. |
| title | Majority dynamics on random graphs: the multiple states case |
| topic | Probability Combinatorics 05C80 |
| url | https://arxiv.org/abs/2311.09078 |