Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 295 - Mathematics Colloquium

Jozsef Balogh

University of Illinois, Urbana-Champaign

Recent Progress in Bootstrap Percolation

Abstract:

\indent Bootstrap percolation is the following deterministic process on a graph $G$. Given a set $A$ of initially `infected' vertices, and a threshold $r \in \mathbb{N}$, new vertices are subsequently infected if they have at least $r$ previously infected neighbours. The study of this model originated in statistical physics, and the process is closely related to the Ising model. The set $A$ is usually chosen randomly, each vertex being infected independently with probability $p \in (0,1)$, and the main aim is to determine the critical probability $p_c(G,r)$ at which percolation (infection of the entire graph) becomes likely to occur.\\ I will give a survey of the area, focusing on the following recent result, proved jointly with Bollobas and Morris:\\ The bootstrap process has been extensively studied on the $d$-dimensional grid $[n]^d$, with $2 \le r \le d$, and it was proved by Cerf and Manzo (building on work of Aizenman and Lebowitz, and Cerf and Cirillo) that $$p_c\big( [n]^d,r \big) \; = \; \Theta\left( \frac{1}{\log_{r-1} n} \right)^{d-r+1},$$ where $\log_{r-1}$ is the $(r-1)$-times iterated logarithm. However, the exact threshold function was only known in the case $d = r = 2$, where it was shown by Holroyd to be $(1 + o(1))\frac{\pi^2}{18\log n}$. In this talk we show how to determine the exact threshold for all fixed $d$ and $r$, concentrating on the crucial case $d = r = 3$.

Hosts: Fan Chung Graham and Jacques Verstraete

February 5, 2009

3:00 PM

AP&M 6402

****************************