Department of
Applied
Mathematics

Extremal Bounds for Bootstrap Percolation in the Hypercube

Jonathan Noel

Abstract

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 present a 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). We will also place this result in context by discussing some of the major results in bootstrap percolation. This is joint work with Natasha Morrison.