An improved upper bound for bootstrap percolation in all dimensions

DOI10.1017/S0963548319000130zbMATH Open1434.60305arXiv1204.3190WikidataQ127665705 ScholiaQ127665705MaRDI QIDQ5222565FDOQ5222565

Authors: Andrew J. Uzzell 

Publication date: 6 April 2020

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

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$.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

• The time of bootstrap percolation with dense initial sets for all thresholds
• 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
• Extremal Bounds for 3-Neighbor Bootstrap Percolation in Dimensions Two and Three

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)