Majority rule cellular automata

Consider a graph G = ( V, E ) and a random initial coloring where each vertex is black independently with probability p b, and white with probability p w = 1 − p b. In each step, all vertices change their current color synchronously to the most frequent color in their neighborhood and in case of a tie, a vertex keeps its current color. This model is called the majority model. If in case of a tie a vertex always selects black color, it is called the biased majority model. We are interested in the behavior of these two processes, especially when the underlying graph is a two-dimensional torus (cellular automaton with (biased) majority rule). In the present paper, as our main result we prove that both majority and biased majority cellular automata exhibit a threshold behavior with two phase transitions. More precisely, we prove for a two-dimensional torus T n, n, there are two threshold values 0 ≤ p 1, p 2 ≤ 1 such that p b ≪ p 1, p 1 ≪ p b ≪ p 2, and p 2 ≪ p b result in final complete occupancy by white, stable coexistence of both colors, and final complete occupancy by black, respectively in O ( n 2 ) number of steps. (For two functions f ( n ) and g ( n ), we shortly write f ( n ) ≪ g ( n ) instead of f ( n ) ∈ o ( g ( n ) ).) We finally argue that our proof techniques can be used to prove a similar threshold behavior for a larger class of models.

Authors

• Bernd Gärtner
• Ahad N. Zehmakan

Keywords

• Cellular automaton
• Majority rule
• Biased majority
• Phase transition
• Bootstrap percolation
• Dynamic monopoly