Benjamini–Chan–O'Donnell–Tamuz conjecture on limiting majority-dynamics cycles

Let G(n,p)G(n,p) be a random graph with vertex set VnV_n, let d=npd=np, and let St(v){1,+1}S_t(v)\in\{-1,+1\} be the state of vertex vv after tt rounds of synchronous majority dynamics. Benjamini–Chan–O'Donnell–Tamuz conjecture. With high probability over the random graph and the initial state, for every sufficiently large nn the following hold: if dd\to\infty, then for every ε>0\varepsilon>0,

limtvVnS2t(v)[(1ε)n,n];\lim_{t\to\infty}\left|\sum_{v\in V_n}S_{2t}(v)\right|\in[(1-\varepsilon)n,n];

if dd is bounded, then for every ε>0\varepsilon>0,

limtvVnS2t(v)[(1ε)n/2,(1+ε)n/2].\lim_{t\to\infty}\left|\sum_{v\in V_n}S_{2t}(v)\right|\in[(1-\varepsilon)n/2,(1+\varepsilon)n/2].

The first regime predicts eventual two-cycles near unanimity, while the bounded-degree regime predicts two-cycles with approximately equal populations of the two states. The paper verifies the first regime under a sufficiently rapid growth condition on dd, but leaves the full conjecture open.

Sources & referencesView supporting material

Primary source

Nikolaos Fountoulakis, Mihyun Kang and Tamás Makai, “Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs”, arXiv:1910.05820 (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.