Benjamini–Chan–O'Donnell–Tamuz conjecture on limiting majority-dynamics cycles
Benjamini–Chan–O'Donnell–Tamuz conjecture on limiting majority-dynamics cycles
Let be a random graph with vertex set , let , and let be the state of vertex after 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 the following hold: if , then for every ,
if is bounded, then for every ,
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 , 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
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.