Majority Dynamics conjecture for oscillating vertices in random regular graphs
Majority Dynamics conjecture for oscillating vertices in random regular graphs
Let be a random -regular graph on vertices, and start Majority Dynamics from a random initial configuration. In a limiting cycle, a vertex is oscillating if its state changes between the two configurations of the cycle, rather than remaining fixed.
Majority Dynamics conjecture. For every , with high probability the number of oscillating vertices lies in
when is odd, and lies in
when is even.
This conjecture describes the experimentally observed parity-dependent behavior of Majority Dynamics on random regular graphs: approximately half the vertices oscillate for odd degree, whereas only a vanishing fraction oscillate for even degree. The statement is presented as a numerical conjecture, and no proof or resolution is given in the source.
Sources & referencesView supporting material
Primary source
Pavel Arkhipov, “Majority Dynamics and Internal Partitions of Random Regular Graphs: Experimental Results”, arXiv:2406.07026 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.