Benjamini–Chan–O'Donnell–Tamuz–Tan conjecture on agreement in majority dynamics
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.