Majority rule cellular automata
METADATA ONLY
Loading...
Author / Producer
Date
2021-10-08
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
Consider a graph G=(V,E) and a random initial coloring where each vertex is black independently with probability pb, and white with probability pw=1−pb. 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 Tn,n, there are two threshold values 0≤p1,p2≤1 such that pb≪p1, p1≪pb≪p2, and p2≪pb result in final complete occupancy by white, stable coexistence of both colors, and final complete occupancy by black, respectively in O(n2) 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.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
889
Pages / Article No.
41 - 59
Publisher
Elsevier
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Cellular automaton; Majority rule; Biased majority; Phase transition; Bootstrap percolation; Dynamic monopoly
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)