Dynamic monopolies of constant size

The paper deals with a polling game on a graph. Initially, each vertex is colored white or black. At each round, each vertex is colored by the color shared by the majority of vertices in its neighborhood. We say that a set of vertices is a dynamic monopoly if starting the game with the vertices of the set colored white, the entire system is white after a finite number of rounds. Peleg asked how small a dynamic monopoly may be as a function of the number of vertices. We show that the answer is O(1).

Abstract licence: CC0

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.