Optimal Power of Few conjecture for majority dynamics

About 3 years old · traced to

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+λ)(log⁡n)/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 p−1/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≥(log⁡n)−1/16p\ge (\log n)^{-1/16}; the general case remains open.

References

Primary source

BaoLinh Tran and Van Vu, “The "Power of Few" Phenomenon: The Sparse Case”, arXiv:2302.05605 (2024).

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.