تقرير
Majority dynamics on random graphs: the multiple states case
| العنوان: | Majority dynamics on random graphs: the multiple states case |
|---|---|
| المؤلفون: | Chellig, Jordan, Fountoulakis, Nikolaos |
| سنة النشر: | 2023 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Probability, Mathematics - 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}$. Comment: 37 pages |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2311.09078 |
| رقم الأكسشن: | edsarx.2311.09078 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |