Majority dynamics and internal partitions of random regular graphs: Experimental results

Arkhipov P. Majority dynamics and internal partitions of random regular graphs: Experimental results. arXiv, 2406.07026.

Download (ext.)

Preprint | Submitted | English
Department
Abstract
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.
Publishing Year
Date Published
2024-06-11
Journal Title
arXiv
Acknowledgement
I am grateful to Matthew Kwan for setting the problem, providing useful literature, fruitful discussions, text review, mentorship, general encouragement and support.
Article Number
2406.07026
IST-REx-ID

Cite this

Arkhipov P. Majority dynamics and internal partitions of random regular graphs: Experimental results. arXiv. doi:10.48550/arXiv.2406.07026
Arkhipov, P. (n.d.). Majority dynamics and internal partitions of random regular graphs: Experimental results. arXiv. https://doi.org/10.48550/arXiv.2406.07026
Arkhipov, Pavel. “Majority Dynamics and Internal Partitions of Random Regular Graphs: Experimental Results.” ArXiv, n.d. https://doi.org/10.48550/arXiv.2406.07026.
P. Arkhipov, “Majority dynamics and internal partitions of random regular graphs: Experimental results,” arXiv. .
Arkhipov P. Majority dynamics and internal partitions of random regular graphs: Experimental results. arXiv, 2406.07026.
Arkhipov, Pavel. “Majority Dynamics and Internal Partitions of Random Regular Graphs: Experimental Results.” ArXiv, 2406.07026, doi:10.48550/arXiv.2406.07026.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 2406.07026

Search this title in

Google Scholar