One-extra-vertex conjecture for majority dynamics

Let Gn,pG_{n,p} be a random graph on nn vertices, and consider majority dynamics from an initial red-blue coloring with more red vertices than blue. For fixed p(0,1)p\in(0,1), let ε>0\varepsilon>0 be a corresponding constant. One-extra-vertex conjecture. With probability at least 0.5+εo(1)0.5+\varepsilon-o(1), the majority dynamics process on Gn,pG_{n,p} 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

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.