Spring 2016

Bootstrap Percolation on Random Graphs

Thursday, May 5, 2016 10:30 am11:15 am PDT

Add to Calendar


Calvin Lab

Bootstrap percolation on a graph $G$ with infection threshold $r$ is a deterministic infection process which evolves in rounds. In each round, every vertex has exactly one of two possible states, either infected or uninfected, and every uninfected vertex $v$ becomes infected if it has at least $r$ infected neighbours, otherwise it remains uninfected. Once a vertex has become infected it remains infected forever. In this talk we shall consider the case when the graph $G$ is a random graph (e.g. binomial random graph $G(n,p)$, random hypergraphs, inhomogeneous random graphs) and show that there exists a critical density of initially infected vertices, below which only a few additional vertices are infected, while above which almost every vertex becomes infected.

PDF icon Bootstrap Percolation on Random Graphs168.49 KB