Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2406.07026 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917690171457536 |
|---|---|
| author | Arkhipov, Pavel |
| author_facet | Arkhipov, Pavel |
| contents | This paper focuses on Majority Dynamics in sparse graphs, in particular, as a tool to study internal cuts. It is known that, in Majority Dynamics on a finite graph, each vertex eventually either comes to a fixed state, or oscillates with period two. The empirical evidence acquired by simulations suggests that for random odd-regular graphs, approximately half of the vertices end up oscillating with high probability. We notice a local symmetry between oscillating and non-oscillating vertices, that potentially can explain why the fraction of the oscillating vertices is concentrated around $\frac{1}{2}$. In our simulations, we observe that the parts of random odd-regular graph under Majority Dynamics with high probability do not contain $\lceil \frac{d}{2} \rceil$-cores at any timestep, and thus, one cannot use Majority Dynamics to prove that internal cuts exist in odd-regular graphs almost surely. However, we suggest a modification of Majority Dynamics, that yields parts with desired cores with high probability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_07026 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Majority Dynamics and Internal Partitions of Random Regular Graphs: Experimental Results Arkhipov, Pavel Combinatorics This paper focuses on Majority Dynamics in sparse graphs, in particular, as a tool to study internal cuts. It is known that, in Majority Dynamics on a finite graph, each vertex eventually either comes to a fixed state, or oscillates with period two. The empirical evidence acquired by simulations suggests that for random odd-regular graphs, approximately half of the vertices end up oscillating with high probability. We notice a local symmetry between oscillating and non-oscillating vertices, that potentially can explain why the fraction of the oscillating vertices is concentrated around $\frac{1}{2}$. In our simulations, we observe that the parts of random odd-regular graph under Majority Dynamics with high probability do not contain $\lceil \frac{d}{2} \rceil$-cores at any timestep, and thus, one cannot use Majority Dynamics to prove that internal cuts exist in odd-regular graphs almost surely. However, we suggest a modification of Majority Dynamics, that yields parts with desired cores with high probability. |
| title | Majority Dynamics and Internal Partitions of Random Regular Graphs: Experimental Results |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.07026 |