## 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: Tuesday, November 21, 2017, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Consider a graph G=(V,E) and an initial random coloring where each vertex is blue with probability p and red otherwise, independently from all other vertices. In each round, all vertices simultaneously switch their color to the most frequent color in their neighborhood and in case of a tie, a vertex keeps its current color. We discuss the behavior of this basic and natural process on the random d-regular graph G_{n,d}. It is shown that for all \epsilon>0, p \le 1/2-\epsilon results in final complete occupancy by red in O(log_d log n) rounds with high probability, provided that d \ge c/\epsilon^2 for a suitable constant c. Furthermore, we argue that with high probability, G_{n,d} is immune; i.e., the smallest dynamic monopoly is of linear size. A dynamic monopoly is a subset of vertices that can take over'' in the sense that a commonly chosen initial color eventually spreads throughout the whole graph, irrespective of the colors of other vertices. This answers an open question of Peleg.