82. Mathematical Colloquium
Béla Bollobás
Cambridge University and University of Memphis
BOOTSTRAP PERCOLATION - RECENT PROBABILISTIC RESULTS
January 8, 2013, 14:00
refektář, 1st floor
Malostranské nám. 25
118 00 Praha 1
Abstract
Bootstrap percolation, a simple cellular automaton introduced by Chalupa, Leath and Reich in 1979, can be viewed as a baby model of the spread of an infection. Let G be a graph, and for every vertex x, let r(x) be a natural number. Starting with a set A0 of `infected' vertices of G at time 0, in bootstrap percolation with threshold function r the infection spreads according to the following deterministic local update rule: a vertex x with at least r(x) infected neighbours at time t becomes infected at time t + 1, and every infected vertex remains infected for ever. The set A percolates if eventually every vertex of G is infected; the first time when every vertex is infected is the time of percolation.
In the past three decades, much work has been done on bootstrap percolation on finite grids of a given dimension in which the initial set A is obtained by selecting its vertices at random, with the same probability p, independently of all other choices. The focus has been on the critical probability, the value of p at which the probability of percolation is 1/2. The first half of my talk will be a review of some of the fundamental results concerning critical probabilities obtained by Aizenman, Lebowitz, Schonman, Cerf, Cirillo, Manzo, Holroyd and others, and by Balogh, Morris, Duminil-Copin and myself. The second half will be about the very recent results I have obtained with Holmgren, Smith and Uzzell on the time a random initial set takes to percolate.
About the speaker
Béla Bollobás is a Fellow of Trinity College, Cambridge, and the Chair of Excellence in Combinatorics at the University of Memphis. He was born in 1943 in Budapest, where he did his undergraduate work. He holds doctorates from Budapest and Cambridge. He has been a Fellow of Trinity College since 1970, and a Chair of Excellence at Memphis since 1995.
He has worked in several areas, including functional analysis, extremal and probabilistic combinatorics, probability theory, percolation and bootstrap percolation. He has proved numerous fundamental results, including the Bishop-Phelps-Bollobás theorem, the cube theorem (with Thomason), the correct order in the Erdös-Stone theorem (with Erdös), the chromatic number of random graphs, the precise nature of the phase transition in the random graph process (with Erdös), the critical probability of random Voronoi percolation in the plane (with Riordan), the Balister-Bollobás entropy inequality, and the critical probability in bootstrap percolation on grids of any dimension and any infection parameter (with Balogh, Duminil-Copin and Morris). He also introduced the interlace polynomial (with Arratia and Sorkin) and the Bollobás-Riordan polynomial, and defined a very general model of inhomogeneous random graphs (with Janson and Riordan). In addition to over 400 papers, he has written ten books, including Modern Graph Theory, Percolation, and The Art of Mathematics. He has had close to 50 Ph.D. students, including the Fields Medallist Tim Gowers, four professors in Cambridge and two in Oxford.
He is a Fellow of the Royal Society, and a Foreign Member of the Hungarian Academy of Sciences. In 2009 he was awarded the Senior Whitehead Prize of the London Mathematical Society.
