# Tight Bounds on the Minimum Size of a Dynamic Monopoly

arXiv: https://arxiv.org/abs/1901.05917 · HTML: https://mlsanity.com/paper/1901.05917/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Dec 2018.

## Built on by (most cited first, 1 of 1)

- [Majority Opinion Diffusion in Social Networks: An Adversarial Approach](https://mlsanity.com/paper/2012.03143/) (2020)

## Abstract (arXiv)

Assume that you are given a graph G=(V,E) with an initial coloring, where each node is black or white. Then, in discrete-time rounds all nodes simultaneously update their color following a predefined deterministic rule. This process is called two-way r-bootstrap percolation, for some integer r, if a node with at least r black neighbors gets black and white otherwise. Similarly, in two-way α-bootstrap percolation, for some 0<α<1, a node gets black if at least α fraction of its neighbors are black, and white otherwise. The two aforementioned processes are called respectively r-bootstrap and α-bootstrap percolation if we require that a black node stays black forever. For each of these processes, we say a node set D is a dynamic monopoly whenever the following holds: If all nodes in D are black then the graph gets fully black eventually. We provide tight upper and lower bounds on the minimum size of a dynamic monopoly.