Optimal Power of Few conjecture for majority dynamics
Optimal Power of Few conjecture for majority dynamics
Let be an Erdős–Rényi random graph, let denote Red's initial advantage, and let satisfy
Optimal Power of Few conjecture. There is a function such that for , tends to as tends to infinity, and, in majority dynamics on with initial advantage for Red, Red wins with probability
This formalizes the claim that an initial advantage of order is sufficient for Red to win with probability bounded away from and that the winning probability approaches as the scaled advantage grows. A result of Sah and Sawhney, improving work of Devlin and Berkowitz, confirms the conjecture when tends to zero sufficiently slowly, namely when ; the general case remains open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
BaoLinh Tran and Van Vu, “The "Power of Few" Phenomenon: The Sparse Case”, arXiv:2302.05605 (2024).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.