Extremal Bounds for Bootstrap Percolation in the Hypercube

04/04/2016 - 16:00
04/04/2016 - 17:00
Jonathan Noel, University of Oxford
McGill University, 805 rue Sherbrooke O, salle/room Burnside 1205

 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.

Last edited by on Thu, 03/31/2016 - 15:31