82 KAM Mathematical Colloquium
Béla Bollobás
Cambridge University and University of Memphis
BOOTSTRAP PERCOLATION - RECENT PROBABILISTIC RESULTS
úterí 8. ledna 2013 ve 14:00, refektář, první patro
KAM MFF UK
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 A_0 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.
O přednášejícím
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
Erdos-Stone
theorem (with Erdos), the chromatic number of random graphs, the precise
na-
ture of the phase transition in the random graph process (with Erdos), 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.