![Counting Complexity and Phase Transitions_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Counting%20Complexity%20and%20Phase%20Transitions_hi-res.jpg?h=bf33d09a&itok=MrH5eN5T)
Abstract
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.