Colloquium: Bootstrap percolation and related graph processes

Bootstrap percolation processes are a family of cellular automata that were originally introduced in 1979 by the physicists Chalupa, Leith and Reich as a model of ferromagnetism. Since then, it has been used throughout a variety of disciplines to model real world phenomena such as the spread of influence in a social network, information processing in neural networks or the spread of a computer virus.

    

The $r$-neighbour bootstrap percolation process on a graph $G$ starts with an initial set $A$ of \emph{infected} vertices and, at each step of the process, a \emph{healthy} vertex becomes infected if it has at least $r$ infected neighbours (once a vertex becomes infected, it remains infected forever). If every vertex of the graph eventually becomes infected, we say that $A$ \emph{percolates}.

    

In this talk I will discuss the solution to a conjecture of Balogh and Bollob\'{a}s that concerns the $r$-neighbour bootstrap process on the $d$-dimensional hypercube. I will also discuss results on related processes, including the weak saturation process introduced by Bollob\'{a}s in 1968, in both the extremal and probabilistic settings.

    

This talk contains work joint with Gal Kronenberg, Taisa Martins, Jonathan Noel and Alex Scott.