Rob Morris
IMPA
Sexta-feira, 27 de abril de 2007, 14:00
Anfiteatro do NUMEC-USP
Resumo:
Bootstrap percolation is a simple monotone process on a graph $G$, which nevertheless exhibits some somewhat surprising behaviour. In this process, vertices become infected over time, or not, depending on the states of their neighbours; the challenge is to determine under which initial conditions the entire vertex set is eventually infected.
The bootstrap process has been extensively studied on the grid, $[n]^d$, where $d$ is fixed and $n \to \infty$, though a sharp threshold for the critical probability has only been determined in the case $d = 2$. In this talk I shall show how to prove a sharp threshold whenever $d \gg \log n \ge 1$. This is joint work with J\'ozsef Balogh and B\'ela Bollob\'as.