The time of bootstrap percolation with dense initial sets

DOI10.1214/12-AOP818MaRDI QIDQ400563zbMATHOpenAlexFDO

Authors Béla Bollobás, Cecilia Holmgren, Andrew J. Uzzell, Paul Smith

Publication date 22 August 2014

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.3922

zbMATH Keywords

Stein-Chen methodbootstrap percolationPoisson convergence result

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05)

Abstract: In r-neighbour bootstrap percolation on the vertex set of a graph G, vertices are initially infected independently with some probability p. At each time step, the infected set expands by infecting all uninfected vertices that have at least r infected neighbours. We study the distribution of the time t at which all vertices become infected. Given t = t(n) = o(log n/log log n), we prove a sharp threshold result for the probability that percolation occurs by time t in d-neighbour bootstrap percolation on the d-dimensional discrete torus T_n^d. Moreover, we show that for certain ranges of p = p(n), the time at which percolation occurs is concentrated either on a single value or on two consecutive values. We also prove corresponding results for the modified d-neighbour rule.

Recommendations

• The time of bootstrap percolation with dense initial sets for all thresholds
• The sharp threshold for bootstrap percolation in all dimensions
• Bootstrap percolation in high dimensions
• The time of bootstrap percolation in two dimensions
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation

Cites work

• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 3438144 (Why is no real title available?)
• scientific article; zbMATH DE number 5066400 (Why is no real title available?)
• scientific article; zbMATH DE number 3076934 (Why is no real title available?)
• A sharper threshold for bootstrap percolation in two dimensions
• Bootstrap percolation in three dimensions
• Bootstrap percolation on the hypercube
• Bootstrap percolation on the random graph \(G_{n,p}\)
• Characteristic exponents for two-dimensional bootstrap percolation
• Compound Poisson approximation for nonnegative random variables via Stein's method
• Convolution bootstrap percolation models, Markov-type stochastic processes, and mock theta functions
• Critical length for semi-oriented bootstrap percolation
• Equivalence of exponential decay rates for bootstrap percolation like cellular automata
• Finite-size effects for anisotropic bootstrap percolation: Logarithmic corrections
• Improved bounds on metastability thresholds and probabilities for generalized bootstrap percolation
• Integrals, partitions, and cellular automata
• Largest and smallest minimal percolating sets in trees
• Largest minimal percolating sets in hypercubes under 2-bootstrap percolation
• Maximal percolation time in hypercubes under 2-bootstrap percolation
• Metastability effects in bootstrap percolation
• Minimal percolating sets in bootstrap percolation
• On slowly percolating sets of minimal size in bootstrap percolation
• On the behavior of some cellular automata related to bootstrap percolation
• On the rate of Poisson convergence
• Poisson approximation for dependent trials
• Poisson approximation for some statistics based on exchangeable trials
• Proof of Straley's argument for bootstrap percolation.
• Random disease on the square grid
• Rates for the probability of large cubes being non-internally spanned in modified bootstrap percolation
• Sharp metastability threshold for an anisotropic bootstrap percolation model
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Sharp thresholds in bootstrap percolation
• Slow convergence in bootstrap percolation
• The Erdős-Rényi law in distribution, for coin tossing and sequence matching
• The metastability threshold for modified bootstrap percolation in \(d\) dimensions
• The sharp threshold for bootstrap percolation in all dimensions
• Two moments suffice for Poisson approximations: The Chen-Stein method

Cited in

(11)

• The maximum time of 2-neighbour bootstrap percolation in grid graphs and parametrized results
• Strong-majority bootstrap percolation on regular graphs with low dissemination threshold
• On slowly percolating sets of minimal size in bootstrap percolation
• The time of bootstrap percolation with dense initial sets for all thresholds
• Approximating dependent rare events
• Sensitive bootstrap percolation second term
• Maximum Percolation Time in Two-Dimensional Bootstrap Percolation
• The Maximum Time of 2-Neighbour Bootstrap Percolation: Complexity Results
• The time of bootstrap percolation in two dimensions
• The maximum time of 2-neighbour bootstrap percolation: algorithmic aspects
• Bootstrap Percolation on Degenerate Graphs

This page was built for publication: The time of bootstrap percolation with dense initial sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q400563)