The bounded-degree almost sure period two conjecture for majority dynamics

Let GG be an infinite graph of bounded degree, and choose the initial opinions independently and uniformly from {1,1}\{-1,1\}. Under majority dynamics, each node's opinion almost surely converges to a cycle of period at most two. Almost sure period two conjecture. Every bounded-degree graph has the almost sure period two property. The conjecture extends the almost sure period two theorem for unimodular transitive graphs to all bounded-degree graphs. The paper gives an infinite counterexample without bounded degree, while the bounded-degree case is left open.

Sources & referencesView supporting material

Primary source

Itai Benjamini, Siu-On Chan, Ryan O'Donnell, Omer Tamuz and Li-Yang Tan, “Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs”, arXiv:1405.2486 (2014).

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.