Benjamini–Chan–O'Donnell–Tamuz–Tan conjecture on agreement in majority dynamics

Let G(n,p)G(n,p) be the Erdős–Rényi random graph on vertex set [n][n], with each edge present independently with probability pp. For each vertex v[n]v\in[n], let s0(v){±1}s_0(v)\in\{\pm1\} be sampled uniformly and independently, and let ε(0,1]\varepsilon\in(0,1]. Under majority dynamics, each opinion st(v)s_t(v) updates synchronously to the majority opinion among the neighbors, retaining its previous value in case of a tie. An (1ε)(1-\varepsilon)-proportion agreement means

vst(v)(12ε)n.\left|\sum_v s_t(v)\right|\geq (1-2\varepsilon)n.

Benjamini–Chan–O'Donnell–Tamuz–Tan conjecture. With probability 1ε1-\varepsilon, the vertices in G(n,p)G(n,p) have an (1ε)(1-\varepsilon)-proportion agreement after sufficiently many days whenever p=ω(1/n)p=\omega(1/n).

The conjecture concerns whether sparse Erdős–Rényi graphs typically drive a uniformly random initial opinion configuration close to consensus. The supplied text gives no evidence of resolution, so its status remains open.

Sources & referencesView supporting material

Primary source

Debsoumya Chakraborti, Jeong Han Kim, Joonkyung Lee and Tuan Tran, “Majority dynamics on sparse random graphs”, arXiv:2105.12709 (2021).

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.