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.

Winter 2016 Schedule