Bootstrap Percolation on Periodic Trees

Bootstrap percolation is a type of cellular automaton which has been used to model various physical phenomena, such as ferromagnetism. For each natural number $r$, the $r$-neighbour bootstrap process is an update rule for vertices of a graph in one of two states: `infected' or `healthy'. In consecutive rounds, each healthy vertex with at least $r$ infected neighbours becomes itself infected. Percolation is said to occur if every vertex is eventually infected. Usually, the s...

We investigate the behaviour of $r$-neighbourhood bootstrap percolation on the binomial $k$-uniform random hypergraph $H_k(n,p)$ for given integers $k\geq 2$ and $r\geq 2$. In $r$-neighbourhood bootstrap percolation, infection spreads through the hypergraph, starting from a set of initially infected vertices, and in each subsequent step of the process every vertex with at least $r$ infected neighbours becomes infected. For our analysis the set of initially infected vertices i...

In dynamical percolation, the status of every bond is refreshed according to an independent Poisson clock. For graphs which do not percolate at criticality, the dynamical sensitivity of this property was analyzed extensively in the last decade. Here we focus on graphs which percolate at criticality, and investigate the dynamical sensitivity of the infinite cluster. We first give two examples of bounded degree graphs, one which percolates for all times at criticality and one w...

We consider Bernoulli bond percolation on a large scale-free tree in the supercritical regime, meaning informally that there exists a giant cluster with high probability. We obtain a weak limit theorem for the sizes of the next largest clusters, extending a recent result for large random recursive trees. The approach relies on the analysis of the asymptotic behavior of branching processes subject to rare neutral mutations, which may be of independent interest.

The Hamming torus of dimension $d$ is the graph with vertices $\{1,\dots,n\}^d$ and an edge between any two vertices that differ in a single coordinate. Bootstrap percolation with threshold $\theta$ starts with a random set of open vertices, to which every vertex belongs independently with probability $p$, and at each time step the open set grows by adjoining every vertex with at least $\theta$ open neighbors. We assume that $n$ is large and that $p$ scales as $n^{-\alpha}$ f...

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

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

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

We investigate bootstrap percolation with infection threshold $r> 1$ on the binomial $k$-uniform random hypergraph $H_k(n,p)$ in the regime $n^{-1}\ll n^{k-2}p \ll n^{-1/r}$, when the initial set of infected vertices is chosen uniformly at random from all sets of given size. We establish a threshold such that if there are less vertices in the initial set of infected vertices, then whp only a few additional vertices become infected, while if the initial set of infected vertice...

Bootstrap percolation is an often used model to study the spread of diseases, rumors, and information on sparse random graphs. The percolation process demonstrates a critical value such that the graph is either almost completely affected or almost completely unaffected based on the initial seed being larger or smaller than the critical value. To analyze intervention strategies we provide the first analytic determination of the critical value for basic bootstrap percolation ...