Optimal Power of Few conjecture for majority dynamics

From papers

Let G(n,p)G(n,p) be an Erdős–Rényi random graph, let Δ\Delta denote Red's initial advantage, and let pp satisfy

p(1+λ)(logn)/n.p \ge (1 + \lambda)(\log n)/n.

Optimal Power of Few conjecture. There is a function f(x)f(x) such that f(x)>1/2f(x)>1/2 for x>0x>0, f(x)f(x) tends to 11 as xx tends to infinity, and, in majority dynamics on G(n,p)G(n,p) with initial advantage Δ\Delta for Red, Red wins with probability

f(Δp).f(\Delta\sqrt{p}).

This formalizes the claim that an initial advantage of order p1/2p^{-1/2} is sufficient for Red to win with probability bounded away from 1/21/2 and that the winning probability approaches 11 as the scaled advantage grows. A result of Sah and Sawhney, improving work of Devlin and Berkowitz, confirms the conjecture when pp tends to zero sufficiently slowly, namely when p(logn)1/16p\ge (\log n)^{-1/16}; 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

No solutions have been posted yet.