One-extra-vertex conjecture for majority dynamics
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.