Benjamini–Chan–O'Donnell–Tamuz–Tan conjecture on agreement in majority dynamics
Let be the Erdős–Rényi random graph on vertex set , with each edge present independently with probability . For each vertex , let be sampled uniformly and independently, and let . Under majority dynamics, each opinion updates synchronously to the majority opinion among the neighbors, retaining its previous value in case of a tie. An -proportion agreement means
Benjamini–Chan–O'Donnell–Tamuz–Tan conjecture. With probability , the vertices in have an -proportion agreement after sufficiently many days whenever .
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
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.