TY - UNPB
T1 - (Biased) Majority Rule Cellular Automata.
AU - Gärtner, Bernd
AU - Zehmakan, Ahad N.
N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2017
Y1 - 2017
N2 - Consider a graph G=(V,E) and a random initial vertex-coloring, where each vertex is blue independently with probability pb, and red with probability pr=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 conserves its current color; this model is called majority model. If in case of a tie a vertex always chooses blue color, it is called biased majority model. We are interested in the behavior of these deterministic processes, especially in a two-dimensional torus (i.e., cellular automaton with (biased) majority rule). In the present paper, as a main result we prove both majority and biased majority cellular automata exhibit a threshold behavior with two phase transitions. More precisely, it is shown that for a two-dimensional torus Tn,n, there are two thresholds 0≤p1,p2≤1 such that pb≪p1, p1≪pb≪p2, and p2≪pb result in monochromatic configuration by red, stable coexistence of both colors, and monochromatic configuration by blue, respectively in O(n2) number of steps
AB - Consider a graph G=(V,E) and a random initial vertex-coloring, where each vertex is blue independently with probability pb, and red with probability pr=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 conserves its current color; this model is called majority model. If in case of a tie a vertex always chooses blue color, it is called biased majority model. We are interested in the behavior of these deterministic processes, especially in a two-dimensional torus (i.e., cellular automaton with (biased) majority rule). In the present paper, as a main result we prove both majority and biased majority cellular automata exhibit a threshold behavior with two phase transitions. More precisely, it is shown that for a two-dimensional torus Tn,n, there are two thresholds 0≤p1,p2≤1 such that pb≪p1, p1≪pb≪p2, and p2≪pb result in monochromatic configuration by red, stable coexistence of both colors, and monochromatic configuration by blue, respectively in O(n2) number of steps
M3 - Working paper
BT - (Biased) Majority Rule Cellular Automata.
ER -