Majority Dynamics conjecture for oscillating vertices in random regular graphs

Let GG be a random dd-regular graph on nn 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 ε>0\varepsilon>0, with high probability the number of oscillating vertices lies in

[(1/2ε)n,(1/2+ε)n][(1/2-\varepsilon)n,(1/2+\varepsilon)n]

when dd is odd, and lies in

[0,εn][0,\varepsilon n]

when dd 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.