| Título: | Bootstrap percolation on Galton-Watson trees |
| Autores: |
Bollobás, Béla; University of Cambridge, University of Memphis, and London Institute for Mathematical Sciences. Gunderson, Karen; University of Bristol Holmgren, Cecilia; Stockholm University and University of Cambridge Janson, Svante; Uppsala University Przykucki, Michał; University of Cambridge and London Institute for Mathematical Sciences |
| Fecha: | 2014-01-02 |
| Publicador: | Electronic journal of probability |
| Fuente: |
 |
| Tipo: | Peer-reviewed Article |
| Tema: |
bootstrap percolation; branching number; infinite trees; Galton--Watson trees 05C05; 60K35; 60C05; 60J80; 05C80 |
| Descripción: | 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, $p_c(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 \geq r$ and for any $\epsilon > 0$ there exists a tree $T$ with branching number $\operatorname{br}(T) = b$ and critical probability $p_c(T,r) < \epsilon$. However, this is false if we limit ourselves to the well studied family of Galton--Watson trees. We show that for every $r \geq 2$ there exists a constant $c_r>0$ such that if $T$ is a Galton- Watson tree with branching number $\operatorname{br}(T) = b \geq r$ then $$p_c(T,r) > \frac{c_r}{b} e^{-\frac{b}{r-1}}.$$ 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 $C_r e^{-\frac{b}{r-1}}$ for some constant $C_r>0$. |
| Idioma: | Inglés |
1 Lévy Classes and Self-Normalization por Khoshnevisan, Davar; University of Utah | 6 Time-Space Analysis of the Cluster-Formation in Interacting Diffusions por Fleischmann, Klaus; Weierstrass Institute for Applied Analysis and Stochastics,Greven, Andreas; Universitat Erlangen-Nurnberg |
2 Hausdorff Dimension of Cut Points for Brownian Motion por Lawler, Gregory F.; Duke University and Cornell University | 7 Conditional Moment Representations for Dependent Random Variables por Bryc, Wlodzimierz; University of Cincinnati |
3 Eigenvalue Expansions for Brownian Motion with an Application to Occupation Times por Bass, Richard F.; University of Washington,Burdzy, Krzysztof; University of Washington | 8 Almost Sure Exponential Stability of Neutral Differential Difference Equations with Damped Stochastic Perturbations por Liao, Xiao Xin; University of Strathclyde,Mao, Xuerong; University of Strathclyde |
4 Random Discrete Distributions Derived from Self-Similar Random Sets por Pitman, Jim; University of California, Berkeley,Yor, Marc; Université Pierre et Marie Curie | 9 Quantitative Bounds for Convergence Rates of Continuous Time Markov Processes por Roberts, Gareth O.; University of Cambridge,Rosenthal, Jeffrey S.; University of Toronto |
5 A Microscopic Model for the Burgers Equation and Longest Increasing Subsequences por Seppäläinen, Timo; Iowa State University | 10 Metastability of the Three Dimensional Ising Model on a Torus at Very Low Temperatures por Ben Arous, Gérard; Ecole Normale Supérieure,Cerf, Raphaël; Université Paris Sud |