One-extra-vertex conjecture for majority dynamics
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.