Bootstrap percolation in high dimensions

In modified two-neighbour bootstrap percolation in two dimensions each site of $\mathbb Z^2$ is initially independently infected with probability $p$ and on each discrete time step one additionally infects sites with at least two non-opposite infected neighbours. In this note we establish that for this model the second term in the asymptotics of the infection time $\tau$ unexpectedly scales differently from the classical two-neighbour model, in which arbitrary two infected ne...

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

In this paper we fill in a fundamental gap in the extremal bootstrap percolation literature, by providing the first proof of the fact that for all $d \geq 1$, the size of the smallest percolating sets in $d$-neighbour bootstrap percolation on $[n]^d$, the $d$-dimensional grid of size $n$, is $n^{d-1}$. Additionally, we prove that such sets percolate in time at most $c_d n^2$, for some constant $c_d >0 $ depending on $d$ only.

Bootstrap percolation is a type of cellular automaton on graphs, introduced as a simple model of the dynamics of ferromagnetism. Vertices in a graph can be in one of two states: `healthy' or `infected' and from an initial configuration of states, healthy vertices become infected by local rules. While the usual bootstrap processes are monotone in the sets of infected vertices, in this paper, a modification is examined in which infected vertices can return to a healthy state. V...

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

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

We study the distribution of the percolation time $T$ of two-neighbour bootstrap percolation on $[n]^2$ with initial set $A\sim\mathrm{Bin}([n]^2,p)$. We determine $T$ with high probability up to a constant factor for all $p$ above the critical probability for percolation, and to within a $1+o(1)$ factor for a large range of $p$.

In the bootstrap percolation model, sites in an L by L square are initially infected independently with probability p. At subsequent steps, a healthy site becomes infected if it has at least 2 infected neighbours. As (L,p)->(infinity,0), the probability that the entire square is eventually infected is known to undergo a phase transition in the parameter p log L, occurring asymptotically at lambda = pi^2/18. We prove that the discrepancy between the critical parameter and its ...