## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, December 15, 2016, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Consider a graph $G=(V,E)$ and a random initial vertex-coloring such that each vertex is blue independently with probability $p_b$, and red with probability $1-p_b$. In each step, all vertices change their current color synchronously to the most frequent color in their neighborhood and in the case of a tie, a vertex becomes blue (a bias toward blue); this model is called biased majority model. We are interested in the behavior of this deterministic process, especially in a two-dimensional torus (cellular automata with biased majority rule). We discuss that biased majority cellular automata exhibit a threshold behavior with two phase transitions. More precisely, it is proved there are two thresholds $0 < p_1 < p_2 < 1$ such that $p_b \ll p_1$, $p_1 \ll p_b \ll p_2$, and $p_2 \ll p_b$ result in final complete occupancy by red, stable coexistence of both colors, and final complete occupancy by blue, respectively. We also present the tight bound of $O(n^2)$ on the consensus time of the process, the time after which the process reaches a periodic sequence of states.