# Bootstrap percolation on Galton–Watson trees

B. Bollobas, K. Gunderson, C. Janson, M. Przykucki

Electronic Journal of Probability 19, 27 (2014)

In bootstrap percolation, a node is infected when a sufficient number of neighbours are infected.

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. In this paper, 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  > 0 there exists a tree T with branching number br(T) = b and critical probability pc(T, r) < . 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 then pc > f(b,cr, r). We also show that this bound is sharp up to a factor of O(b) by giving an explicit family of Galton–Watson trees with critical probability bounded from above by some constant Cr > 0.

#### Degree-correlations in a bursting dynamic network model

F. Vanni, P. Barucca

Journal of Economic Interaction and Coordination

#### Phase transition creates the geometry of the continuum from discrete space

R. Farr, T. Fink

Physical Review E

#### Intelligently chosen interventions have potential to outperform the diode bridge in power conditioning

F. Liu, Y. Zhang, O. Dahlsten, F. Wang

Scientific Reports

#### Scale of non-locality for a system of n particles

S. Talaganis, I. Teimouri

Sub. to Physical Review D

#### Portfolio analysis and geographical allocation of renewable sources: A stochastic approach

A. Scala, A. Facchini, U. Perna, R. Basosi

Energy Policy

#### Changes to Gate Closure and its impact on wholesale electricity prices: The case of the UK

A. Facchini, A. Rubino, G. Caldarelli, G. Liddo

Energy Policy

#### How much can we influence the rate of innovation?

T. Fink, M. Reeves

#### The statistical physics of real-world networks

G. Cimini, T. Squartini, F. Saracco, D. Garlaschelli, A. Gabrielli, G. Caldarelli

Nature Reviews Physics

#### Memristive networks: from graph theory to statistical physics

A. Zegarac, F. Caravelli

EPL

#### PopRank: Ranking pages’ impact and users’ engagement on Facebook

A. Zaccaria, M. Vicario, W. Quattrociocchi, A. Scala, L. Pietronero

PLoS ONE

128 / 128 papers