Bootstrap Percolation on Periodic Trees

Consider a $p$-random subset $A$ of initially infected vertices in the discrete cube $[L]^d$, and assume that the neighbourhood of each vertex consists of the $a_i$ nearest neighbours in the $\pm e_i$-directions for each $i \in \{1,2,\dots, d\}$, where $a_1\le a_2\le \dots \le a_d$. Suppose we infect any healthy vertex $v\in [L]^d$ already having $r$ infected neighbours, and that infected sites remain infected forever. In this paper we determine the $(d-1)$-times iterated log...

We study Bernoulli bond percolation on a random recursive tree of size $n$ with percolation parameter $p(n)$ converging to $1$ as $n$ tends to infinity. The sizes of the percolation clusters are naturally stored in a tree. We prove convergence in distribution of this tree to the genealogical tree of a continuous-state branching process in discrete time. As a corollary we obtain the asymptotic sizes of the largest and next largest percolation clusters, extending thereby a rece...

Majority bootstrap percolation on the random graph $G_{n,p}$ is a process of spread of "activation" on a given realisation of the graph with a given number of initially active nodes. At each step those vertices which have more active neighbours than inactive neighbours become active as well. We study the size $A^*$ of the final active set. The parameters of the model are, besides $n$ (tending to $\infty$), the size $A(0)=A_0(n)$ of the initially active set and the probabili...

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

Bootstrap percolation is a process that is used to model the spread of an infection on a given graph. In the model considered here each vertex is equipped with an individual threshold. As soon as the number of infected neighbors exceeds that threshold, the vertex gets infected as well and remains so forever. We perform a thorough analysis of bootstrap percolation on a novel model of directed and inhomogeneous random graphs, where the distribution of the edges is specified by ...

Bootstrap percolation on the random graph $G_{n,p}$ is a process of spread of "activation" on a given realization of the graph with a given number of initially active nodes. At each step those vertices which have not been active but have at least $r\geq2$ active neighbors become active as well. We study the size $A^*$ of the final active set. The parameters of the model are, besides $r$ (fixed) and $n$ (tending to $\infty$), the size $a=a(n)$ of the initially active set and t...

We analyze the metastable states near criticality of the bootstrap percolation on Galton-Watson trees. We find that, depending on the exact choice of the offspring distribution, it is possible to have several distinct metastable states, with varying scaling of their duration while approaching criticality.

In this paper a random graph model $G_{\mathbb{Z}^2_N,p_d}$ is introduced, which is a combination of fixed torus grid edges in $(\mathbb{Z}/N \mathbb{Z})^2$ and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices $u,v\in(\mathbb{Z}/N \mathbb{Z})^2$ with graph distance $d$ on the torus grid is $p_d=c/Nd$, where $c$ is some constant. We show that, {\em whp}, the diameter $D(G_{\mathbb{Z}^2_N,p_d})=\Theta (\lo...

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

Graph bootstrap percolation is a deterministic cellular automaton which was introduced by Bollob\'as in 1968, and is defined as follows. Given a graph $H$, and a set $G \subset E(K_n)$ of initially `infected' edges, we infect, at each time step, a new edge $e$ if there is a copy of $H$ in $K_n$ such that $e$ is the only not-yet infected edge of $H$. We say that $G$ percolates in the $H$-bootstrap process if eventually every edge of $K_n$ is infected. The extremal questions fo...