BOOTSTRAP PERCOLATION 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 starting set of infected vertices is chosen at random, with all vertices initially infected independently with probability p. In that case, given a graph G and infection threshold r, a quantity of interest is the critical probability, pc(G,r), at which percolation becomes likely to occur. Here we look at infinite trees and, answering a problem posed by Balogh, Peres and Pete, we show that for any b ≥ r and for any e > 0 there exists a tree T with branching number br(T) = b and critical probability pc(T, r) < e. However, this is false if we limit ourselves to the well-studied family of Galton–Watson trees. We show that for
every r ≥ 2 there exists a constant cr > 0 such that if T is a Galton–Watson tree with branching number br(T) = b ≥ r

LINE PERCOLATION is  a geometric bootstrap percolation model, line percolation, on the d-dimensional grid [n]d. In line percolation with infection parameter r, infection spreads from a subset A[n]^d of initially infected lattice points as follows: if there is an axis parallel line L with r or more infected lattice points on it, then every lattice point of [n]d on L gets infected and we repeat this until the infection can no longer spread.

The elements of the set A are usually chosen independently, with some density p, and the main question is to determine pc(n, r, d), the
density at which percolation (infection of the entire grid) becomes likely. Let qp(n,r,d) denote the probability that such randomly chosen initial set Ap percolates. We define the critical probability pc(n,r,d) by setting
pc(n,r,d)=inf{p: qp(n,r,d)≥½} We can determine pc(n, r, 2) up to a factor of 1+o(1) as n-->∞ . We also determine the size
of the minimal percolating sets in all dimensions and for all values of the infection
parameter.

SUBCRITICAL U-BOOTSTRAP PERCOLATION We prove that there exist natural generalizations of the classical bootstrap percolation model on ℤ! that have non-trivial critical probabilities, and moreover we characterize all homogeneous, local, monotone models with this property.
Van Enter (in the case d=r=2) and Schonmann (for all d>r>2) proved that r-neighbour bootstrap percolation models have trivial critical probabilities on ℤ! for every choice of the parameters d>r>2: that is, an initial set of density p almost surely percolates ℤ! for every p > 0. These results effectively ended the study of bootstrap percolation on infinite lattices.
Recently Bollobás, Smith and Uzzell introduced a broad class of percolation models called U-bootstrap percolation, which includes r-neighbour bootstrap percolation as a special case. They divided two-dimensional U-bootstrap percolation models into three classes –subcritical, critical and supercritical – and they proved that, like classical 2-neighbour bootstrap percolation, critical and supercritical U-bootstrap percolation models have trivial critical probabilities on ℤ!. They left open the question as to what happens in the case of subcritical families. In this paper we answer that question: we show that every subcritical Ubootstrap percolation model has a non-trivial critical probability on ℤ!. This is new except for a certain ‘degenerate’ subclass of symmetric models that can be coupled from below with oriented site percolation.

### Articles on

• #### Game Theory (0)

 We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy. I accept cookies from this site. Agree 