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

About 5 years old · traced to

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)∣≥(1−2ε)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.

References

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.