Abstract
Bootstrap percolation is a type of cellular automaton on graphs, introduced as a
simple model of the dynamics of ferromagnetism. Vertices in a graph can be in one of two
states: ‘healthy’ or ‘infected’ and from an initial configuration of states, healthy vertices
become infected by local rules. While the usual bootstrap processes are monotone in the sets of infected vertices, in this paper, a modification is examined in which infected vertices can return to a healthy state. Vertices are initially infected independently at random and the central question is whether all vertices eventually become infected. The model examined here is such a process on a square grid for which healthy vertices with at least two infected neighbours become infected and infected vertices with no infected neighbours become healthy. Sharp thresholds are given for the critical probability of initial infections for all vertices eventually to become infected.
simple model of the dynamics of ferromagnetism. Vertices in a graph can be in one of two
states: ‘healthy’ or ‘infected’ and from an initial configuration of states, healthy vertices
become infected by local rules. While the usual bootstrap processes are monotone in the sets of infected vertices, in this paper, a modification is examined in which infected vertices can return to a healthy state. Vertices are initially infected independently at random and the central question is whether all vertices eventually become infected. The model examined here is such a process on a square grid for which healthy vertices with at least two infected neighbours become infected and infected vertices with no infected neighbours become healthy. Sharp thresholds are given for the critical probability of initial infections for all vertices eventually to become infected.
Original language | English |
---|---|
Pages (from-to) | 531-570 |
Number of pages | 40 |
Journal | Journal of Statistical Physics |
Volume | 157 |
Early online date | 4 Sept 2014 |
DOIs | |
Publication status | Published - 2014 |
Keywords
- cellular automata
- bootstrap percolation
- sharp threshold