TCS Journal 2021 Journal Article
Majority rule cellular automata
- Bernd Gärtner
- Ahad N. Zehmakan
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.