Graph bootstrap percolation

A bootstrap percolation process on a graph G is an "infection" process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round every uninfected node which has at least r infected neighbours becomes infected and remains so forever. The parameter r > 1 is fixed. We consider this process in the case where the underlying graph is an inhomogeneous random graph whose kernel is of rank 1. Assuming that initially every vertex is infected...

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 ...

Given two graphs $G$ and $H$, it is said that $G$ percolates in $H$-bootstrap process if one could join all the nonadjacent pairs of vertices of $G$ in some order such that a new copy of $H$ is created at each step. Balogh, Bollob\'as and Morris in 2012 investigated the threshold of $H$-bootstrap percolation in the Erd\H{o}s-R\'enyi model for the complete graph $H$ and proposed the similar problem for $H=K_{s,t}$, the complete bipartite graph. In this paper, we provide lower ...

On a geometric model for complex networks (introduced by Krioukov et al.) we investigate the bootstrap percolation process. This model consists of random geometric graphs on the hyperbolic plane having $N$ vertices, a dependent version of the Chung-Lu model. The process starts with infection rate $p=p(N)$. Each uninfected vertex with at least $\mathbf{r}\geq 1$ infected neighbors becomes infected, remaining so forever. We identify a function $p_c(N)=o(1)$ such that a.a.s.\ wh...

Majority bootstrap percolation on a graph $G$ is an epidemic process defined in the following manner. Firstly, an initially infected set of vertices is selected. Then step by step the vertices that have more infected than non-infected neighbours are infected. We say that percolation occurs if eventually all vertices in $G$ become infected. In this paper we study majority bootstrap percolation on the Erd\H{o}s-R\'enyi random graph $G(n,p)$ above the connectivity threshold. P...

In this paper we focus on $r$-neighbor bootstrap percolation, which is a process on a graph where initially a set $A_0$ of vertices gets infected. Now subsequently, an uninfected vertex becomes infected if it is adjacent to at least $r$ infected vertices. Call $A_f$ the set of vertices that is infected after the process stops. More formally set $A_t:=A_{t-1}\cup \{v\in V: |N(v)\cap A_{t-1}|\geq r\}$, where $N(v)$ is the neighborhood of $v$. Then $A_f=\bigcup_{t>0} A_t$. We de...

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...

Majority bootstrap percolation is a monotone cellular automata that can be thought of as a model of infection spreading in networks. Starting with an initially infected set, new vertices become infected once more than half of their neighbours are infected. The average case behaviour of this process was studied on the $n$-dimensional hypercube by Balogh, Bollob\'{a}s and Morris, who showed that there is a phase transition as the typical density of the initially infected set in...

We study the percolation time of the $r$-neighbour bootstrap percolation model on the discrete torus $(\Z/n\Z)^d$. For $t$ at most a polylog function of $n$ and initial infection probabilities within certain ranges depending on $t$, we prove that the percolation time of a random subset of the torus is exactly equal to $t$ with high probability as $n$ tends to infinity. Our proof rests crucially on three new extremal theorems that together establish an almost complete understa...

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$.