An improved upper bound for bootstrap percolation in all dimensions

DOI10.1017/S0963548319000130MaRDI QIDQ5222565zbMATH OpenWikidataFDO

Authors Andrew J. Uzzell

Publication date 6 April 2020

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: In $r$-neighbor bootstrap percolation on the vertex set of a graph $G$, a set $A$ of initially infected vertices spreads by infecting, at each time step, all uninfected vertices with at least $r$ previously infected neighbors. When the elements of $A$ are chosen independently with some probability $p$, it is natural to study the critical probability $p_c(G,r)$ at which it becomes likely that all of $V(G)$ will eventually become infected. Improving a result of Balogh, Bollob'as, and Morris, we give a bound on the second term in the expansion of the critical probability when $G=[n{]}^d$ and $dgeqrgeq2$. We show that for all $dgeqrgeq2$ there exists a constant $c_{d,r}>0$ such that if $n$ is sufficiently large, then [ p_c([n]^d, r) leq Biggl(dfrac{lambda(d,r)}{log_{(r-1)}(n)} - dfrac{c_{d,r}}{�igl(log_{(r-1)}(n)�igr)^{3/2}}Biggr)^{d-r+1}, ] where $lambda(d,r)$ is an exact constant and $lo{g}_{(k)}(n)$ denotes the $k$-times iterated natural logarithm of $n$.

Recommendations

• Bootstrap percolation in high dimensions
• The sharp threshold for bootstrap percolation in all dimensions
• Bootstrap percolation in three dimensions
• The second term for two-neighbour bootstrap percolation in two dimensions
• Extremal bounds for bootstrap percolation in the hypercube

Cites work

• A sharper threshold for bootstrap percolation in two dimensions
• Bootstrap percolation in three dimensions
• Finite size scaling in three-dimensional bootstrap percolation
• Higher order corrections for anisotropic bootstrap percolation
• Metastability effects in bootstrap percolation
• Metastability thresholds for anisotropic bootstrap percolation in three dimensions
• Monotone cellular automata in a random environment
• On the behavior of some cellular automata related to bootstrap percolation
• Proof of Straley's argument for bootstrap percolation.
• Random disease on the square grid
• Sharp metastability threshold for an anisotropic bootstrap percolation model
• Sharp metastability threshold for two-dimensional bootstrap percolation
• Slow convergence in bootstrap percolation
• Stretched exponential fixation in stochastic Ising models at zero temperature
• Subcritical \(\mathcal{U}\)-bootstrap percolation models have non-trivial phase transitions
• The metastability threshold for modified bootstrap percolation in d dimensions
• The second term for two-neighbour bootstrap percolation in two dimensions
• The sharp threshold for bootstrap percolation in all dimensions
• The sharp threshold for the Duarte model
• The threshold regime of finite volume bootstrap percolation.
• Zero-temperature Glauber dynamics on \({\mathbb{Z}^d}\)

Cited in

(9)

• Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three
• The time of bootstrap percolation with dense initial sets for all thresholds
• The \(d\)-dimensional bootstrap percolation models with axial neighbourhoods
• Lower bounds for bootstrap percolation on Galton-Watson trees
• Bootstrap percolation on a graph with random and local connections
• The Application of Non-Crossing Partitions to Improving Percolation Threshold Bounds
• Polluted bootstrap percolation with threshold two in all dimensions
• Sharp threshold for the FA-2f kinetically constrained model
• Bootstrap percolation in high dimensions

This page was built for publication: An improved upper bound for bootstrap percolation in all dimensions

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