Breadcrumb
Maximum percolation time in bootstrap percolation
Thu 25 April 2013, 16:30
Michal Przykucki
University of Cambridge
Organisers: Tom McCourt, Tony Nixon, Karen Gunderson
ABSTRACT
(joint work with Fabricio Benevides)
Bootstrap percolation is one of the simplest cellular automata. In r-neighbour bootstrap percolation on a graph G an infection spreads according to the following deterministic rule: infected vertices of G remain infected forever and in consecutive rounds healthy vertices with at least r already infected neighbours become infected. Percolation occurs if eventually every vertex is infected.
In this talk we focus on extremal problems in 2-neighbour bootstrap percolation and present our recent results about the maximum time this process can take to percolate in the n by n square grid and in the n-dimensional hypercube graph.