One-extra-vertex conjecture for majority dynamics
Let be a random graph on vertices, and consider majority dynamics from an initial red-blue coloring with more red vertices than blue. For fixed , let be a corresponding constant. One-extra-vertex conjecture. With probability at least , the majority dynamics process on eventually makes all vertices red. This would extend the paper's result for an initial lead of three vertices to any positive initial lead, and likely requires a new approach.
References
Primary source
Ross Berkowitz and Pat Devlin, “Central Limit Theorem for Majority Dynamics: Bribing Three Voters Suffices”, arXiv:2010.08172 (2020).
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
No solutions have been posted yet.