Monday, April 4th, 2016 | 4pm-5pm | Burnside 1205 |

University of Oxford

Extremal Bounds for Bootstrap Percolation in the Hypercube

The r-neighbour bootstrap process on a graph G begins with an initial set of "infected" vertices and, at each step of the process, a previously healthy vertex becomes infected if it has at least r infected neighbours. The set of initially infected vertices is said to "percolate" if the infection spreads to the entire vertex set. In this talk, we will discuss a recent proof of a conjecture of Balogh and Bollobás which says that the minimum size of a percolating set for the r-neighbour bootstrap process in the d-dimensional hypercube is asymptotically (1/r) (d choose r-1). The proof boils down to defining an analogous process on the edges of the hypercube and doing a nice "linear algebra trick." We will also place this result in context by discussing some of the known results in the field. This is joint work with Natasha Morrison.