Graph bootstrap percolation

Graph bootstrap percolation, introduced by Bollob\'as in 1968, is a cellular automaton defined as follows. Given a "small" graph $H$ and a "large" graph $G = G_0 \subseteq K_n$, in consecutive steps we obtain $G_{t+1}$ from $G_t$ by adding to it all new edges $e$ such that $G_t \cup e$ contains a new copy of $H$. We say that $G$ percolates if for some $t \geq 0$, we have $G_t = K_n$. For $H = K_r$, the question about the size of the smallest percolating graphs was independe...

Graph bootstrap percolation is a simple cellular automaton introduced by Bollob\'as in 1968. Given a graph $H$ and a set $G \subseteq E(K_n)$ we initially "infect" all edges in $G$ and then, in consecutive steps, we infect every $e \in K_n$ that completes a new infected copy of $H$ in $K_n$. We say that $G$ percolates if eventually every edge in $K_n$ is infected. The extremal question about the size of the smallest percolating sets when $H = K_r$ was answered independently b...

The process of $H$-bootstrap percolation for a graph $H$ is a cellular automaton, where, given a subset of the edges of $K_n$ as initial set, an edge is added at time $t$ if it is the only missing edge in a copy of $H$ in the graph obtained through this process at time $t-1$. We discuss an extremal question about the time of $K_r$-bootstrap percolation, namely determining maximal times for an $n$-vertex graph before the process stops. We determine exact values for $r=4$ and f...

In the random $r$-neighbour bootstrap percolation process on a graph $G$, a set of initially infected vertices is chosen at random by retaining each vertex of $G$ independently with probability $p\in (0,1)$, and "healthy" vertices get infected in subsequent rounds if they have at least $r$ infected neighbours. A graph $G$ \emph{percolates} if every vertex becomes eventually infected. A central problem in this process is to determine the critical probability $p_c(G,r)$, at whi...

By bootstrap percolation we mean the following deterministic process on a graph $G$. Given a set $A$ of vertices "infected" at time 0, new vertices are subsequently infected, at each time step, if they have at least $r\in\mathbb{N}$ previously infected neighbors. When the set $A$ is chosen at random, 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. This bootstrap process has been ext...

For fixed $r\geq 2$, we consider bootstrap percolation with threshold $r$ on the Erd\H{o}s-R\'enyi graph ${\cal G}_{n,p}$. We identify a threshold for $p$ above which there is with high probability a set of size $r$ which can infect the entire graph. This improves a result of Feige, Krivelevich and Reichman, which gives bounds for this threshold, up to multiplicative constants. As an application of our results, we also obtain an upper bound for the threshold for $K_4$-boots...

In r-neighbour bootstrap percolation on a graph G, a set of initially infected vertices A \subset V(G) is chosen independently at random, with density p, and new vertices are subsequently infected if they have at least r infected neighbours. The set A is said to percolate if eventually all vertices are infected. Our aim is to understand this process on the grid, [n]^d, for arbitrary functions n = n(t), d = d(t) and r = r(t), as t -> infinity. The main question is to determine...

In $r$-neighbor bootstrap percolation on the vertex set of a graph $G$, a set $A$ of initially infected vertices spreads by infecting, at each time step, all uninfected vertices with at least $r$ previously infected neighbors. When the elements of $A$ are chosen independently with some probability $p$, it is natural to study the critical probability $p_c(G,r)$ at which it becomes likely that all of $V(G)$ will eventually become infected. Improving a result of Balogh, Bollob\'...

Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollob\'as in 1968. In this process, we start with initial "infected" set of edges $E_0$, and we infect new edges according to a predetermined rule. Given a graph $H$ and a set of previously infected edges $E_t\subseteq E(K_n)$, we infect a non-infected edge $e$ if it completes a new copy of $H$ in $G=([n],E_t\cup e)$. A question raised by Bollob\'as asks for the maximum time the process can run bef...

We locate the critical threshold $p_c$ at which it becomes likely that the complete graph $K_n$ can be obtained from the Erd\H{o}s-R\'enyi graph ${\cal G}_{n,p}$ by iteratively completing copies of $K_4$ minus an edge. This refines work of Balogh, Bollob\'as and Morris that bounds the threshold up to multiplicative constants.