The time of graph bootstrap percolation

In majority bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: if at least half of the neighbours of a vertex v are already infected, then v is also infected, and infected vertices remain infected forever. Percolation occurs if eventually every vertex is infected. The elements of the set of initially infected vertices, A \subset V(G), are normally chosen independently at random, each with probability p, say. This process ...

In $H$-percolation, we start with an Erd\H{o}s--R\'enyi graph ${\mathcal G}_{n,p}$ and then iteratively add edges that complete copies of $H$. The process percolates if all edges missing from ${\mathcal G}_{n,p}$ are eventually added. We find the critical threshold $p_c$ when $H={\mathcal G}_{k,1/2}$ is uniformly random, solving a problem of Balogh, Bollob\'as and Morris.

In the $r$-neighbour bootstrap process on a graph $G$, vertices are infected (in each time step) if they have at least $r$ already-infected neighbours. Motivated by its close connections to models from statistical physics, such as the Ising model of ferromagnetism, and kinetically constrained spin models of the liquid-glass transition, the most extensively-studied case is the two-neighbour bootstrap process on the two-dimensional grid $[n]^2$. Around 15 years ago, in a major ...

The $r$-edge bootstrap percolation on a graph is an activation process of the edges. The process starts with some initially activated edges and then, in each round, any inactive edge whose one of endpoints is incident to at least $r$ active edges becomes activated. A set of initially activated edges leading to the activation of all edges is said to be a percolating set. Denote the minimum size of a percolating set in the $r$-edge bootstrap percolation process on a graph $G$ b...

For any integer $r\geqslant0$, the $r$-neighbor bootstrap percolation on a graph is an activation process of the vertices. The process starts with some initially activated vertices and then, in each round, any inactive vertex with at least $r$ active neighbors becomes activated. A set of initially activated vertices leading to the activation of all vertices is said to be a percolating set. Denote the minimum size of a percolating set in the $r$-neighbor bootstrap percolation ...

Motivated by the bootstrap percolation process for graphs, we define a new, high-order generalisation to $k$-uniform hypergraphs, in which we infect $j$-sets of vertices for some integer $1\le j \le k-1$. We investigate the smallest possible size of an initially infected set which ultimately percolates and determine the exact size in almost all cases of $k$ and $j$.

The $r$-neighbour bootstrap percolation process on a graph $G$ starts with an initial set $A_0$ of "infected" vertices and, at each step of the process, a healthy vertex becomes infected if it has at least $r$ infected neighbours (once a vertex becomes infected, it remains infected forever). If every vertex of $G$ eventually becomes infected, then we say that $A_0$ percolates. We prove a conjecture of Balogh and Bollob\'as which says that, for fixed $r$ and $d\to\infty$, ev...

Given $r\geq2$ and an $r$-uniform hypergraph $F$, the $F$-bootstrap process starts with an $r$-uniform hypergraph $H$ and, in each time step, every hyperedge which "completes" a copy of $F$ is added to $H$. The maximum running time of this process has been recently studied in the case that $r=2$ and $F$ is a complete graph by Bollob\'as, Przykucki, Riordan and Sahasrabudhe [Electron. J. Combin. 24(2) (2017), Paper No. 2.16], Matzke [arXiv:1510.06156v2] and Balogh, Kronenberg,...

In r-neighbour bootstrap percolation on a graph G, a (typically random) set A of initially 'infected' vertices spreads by infecting (at each time step) vertices with at least r already-infected neighbours. This process may be viewed as a monotone version of the Glauber dynamics of the Ising model, and has been extensively studied on the d-dimensional grid $[n]^d$. The elements of the set A are usually chosen independently, with some density p, and the main question is to dete...

We introduce a simple method for proving lower bounds for the size of the smallest percolating set in a certain graph bootstrap process. We apply this method to determine the sizes of the smallest percolating sets in multidimensional tori and multidimensional grids (in particular hypercubes). The former answers a question of Morrison and Noel, and the latter provides an alternative and simpler proof for one of their main results.