## Abstract

Bootstrap percolation on an arbitrary graph has a random initial configuration, where each vertex is occupied with probability p, independently of each other, and a deterministic spreading rule with a fixed parameter k: if a vacant site has at least k occupied neighbours at a certain time step, then it becomes occupied in the next step. This process is well studied on ℤ^{d}; here we investigate it on regular and general infinite trees and on non-amenable Cayley graphs. The critical probability is the infimum of those values of p for which the process achieves complete occupation with positive probability. On trees we find the following discontinuity: if the branching number of a tree is strictly smaller than k, then the critical probability is 1, while it is 1 -1/k on the k-ary tree. A related result is that in any rooted tree T there is a way of erasing k children of the root, together with all their descendants, and repeating this for all remaining children, and so on, such that the remaining tree T′ has branching number br(T′) ≤ max{br(T) - k, 0}. We also prove that on any 2k-regular non-amenable graph, the critical probability for the k-rule is strictly positive.

Original language | English (US) |
---|---|

Pages (from-to) | 715-730 |

Number of pages | 16 |

Journal | Combinatorics Probability and Computing |

Volume | 15 |

Issue number | 5 |

DOIs | |

State | Published - Sep 2006 |

Externally published | Yes |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics