Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
From MaRDI portal
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 neighbors at a certain time step, then it becomes occupied in the next step. This process is well-studied on Z^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 general 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 �r(T') leq max (�r(T)-k, 0). We also prove that on any 2k-regular non-amenable graph, the critical probability for the k-rule is strictly positive.
Recommendations
Cited in
(54)- Bootstrap percolation and kinetically constrained models on hyperbolic lattices
- New bounds for contagious sets
- Metastable behavior of bootstrap percolation on Galton-Watson trees
- Graph bootstrap percolation
- Triggering cascades on undirected connected graphs
- A note on bootstrap percolation thresholds in plane tilings using regular polygons
- The Routing of Complex Contagion in Kleinberg’s Small-World Networks
- A phase transition regarding the evolution of bootstrap processes in inhomogeneous random graphs
- Threshold \(\theta \geq 2\) contact processes on homogeneous trees
- Percolation on complex networks: theory and application
- Scaling and inverse scaling in anisotropic bootstrap percolation
- BOOTSTRAP PERCOLATION ON RANDOM GEOMETRIC GRAPHS
- Percolation in bipartite Boolean networks and its role in sustaining life
- Mixing time of a kinetically constrained spin model on trees: power law scaling at criticality
- Cyclic cellular automata and Greenberg-Hastings models on regular trees
- Strict Majority Bootstrap Percolation on Augmented Tori and Random Regular Graphs: Experimental Results
- Triangle percolation on the grid
- Bootstrap percolation on homogeneous trees has 2 phase transitions
- Bootstrap percolation in directed inhomogeneous random graphs
- Bootstrap percolation with inhibition
- Bootstrap percolation, connectivity, and graph distance
- Metastable behavior for bootstrap percolation on regular trees
- Sharp thresholds for contagious sets in random graphs
- Bootstrap percolation on Galton-Watson trees
- Bootstrap percolation on a graph with random and local connections
- Spread of infection over P.A. random graphs with edge insertion
- Normalization phenomena in asynchronous networks
- A sharper threshold for bootstrap percolation in two dimensions
- Bootstrap percolation on the stochastic block model
- \(k\)-independent percolation on trees
- The sharp threshold for bootstrap percolation in all dimensions
- Bootstrap percolation in living neural networks
- Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)
- Coarsening model on \({\mathbb{Z}^{d}}\) with biased zero-energy flips and an exponential large deviation bound for ASEP
- Majority Bootstrap Percolation on the Hypercube
- Bootstrap percolation on the random graph \(G_{n,p}\)
- The set of solutions of random XORSAT formulae
- Minimum 2-percolating sets in 2-connected, diameter 2 graphs
- Bootstrap percolation in three dimensions
- Majority dynamics on trees and the dynamic cavity method
- Deterministic bootstrap percolation on trees
- Bootstrap percolation on the high-dimensional Hamming graph
- Bootstrap Percolation on Degenerate Graphs
- Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
- Bootstrap percolation in high dimensions
- Monotone cellular automata in a random environment
- Kinetically constrained spin models on trees
- Dynamical Gibbs-non-Gibbs transitions in Widom-Rowlinson models on trees
- An asynchronous linear-threshold innovation diffusion model
- Recent advances in percolation theory and its applications
- A trust model for spreading gossip in social networks: a multi-type bootstrap percolation model
- Bootstrap percolation in power-law random graphs
- Bootstrap percolation in inhomogeneous random graphs
- Universality for two‐dimensional critical cellular automata
This page was built for publication: Bootstrap Percolation on Infinite Trees and Non-Amenable Groups
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3412104)
