2024/06/11 by Arkhipov, Pavel
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2406.07026
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 (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 (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.