ID: 2303.14910

Sensitive bootstrap percolation second term

March 27, 2023

View on ArXiv
Ivailo Hartarsky
Mathematics
Probability

In modified two-neighbour bootstrap percolation in two dimensions each site of $\mathbb Z^2$ is initially independently infected with probability $p$ and on each discrete time step one additionally infects sites with at least two non-opposite infected neighbours. In this note we establish that for this model the second term in the asymptotics of the infection time $\tau$ unexpectedly scales differently from the classical two-neighbour model, in which arbitrary two infected neighbours are required. More precisely, we show that for modified bootstrap percolation with high probability as $p\to0$ it holds that \[\tau\le \exp\left(\frac{\pi^2}{6p}-\frac{c\log(1/p)}{\sqrt p}\right)\] for some positive constant $c$, while the classical model is known to lack the logarithmic factor.

Similar papers 1

Slow Convergence in Bootstrap Percolation

May 9, 2007

91% Match
Janko Gravner, Alexander E. Holroyd
Probability
Mathematical Physics

In the bootstrap percolation model, sites in an L by L square are initially infected independently with probability p. At subsequent steps, a healthy site becomes infected if it has at least 2 infected neighbours. As (L,p)->(infinity,0), the probability that the entire square is eventually infected is known to undergo a phase transition in the parameter p log L, occurring asymptotically at lambda = pi^2/18. We prove that the discrepancy between the critical parameter and its ...

Find SimilarView on arXiv

A sharper threshold for bootstrap percolation in two dimensions

February 20, 2010

91% Match
Janko Gravner, Alexander E. Holroyd, Robert Morris
Probability
Combinatorics

Two-dimensional bootstrap percolation is a cellular automaton in which sites become 'infected' by contact with two or more already infected nearest neighbors. We consider these dynamics, which can be interpreted as a monotone version of the Ising model, on an n x n square, with sites initially infected independently with probability p. The critical probability p_c is the smallest p for which the probability that the entire square is eventually infected exceeds 1/2. Holroyd de...

Find SimilarView on arXiv

The second term for two-neighbour bootstrap percolation in two dimensions

June 23, 2018

90% Match
Ivailo Hartarsky, Robert Morris
Probability
Combinatorics

In the $r$-neighbour bootstrap process on a graph $G$, vertices are infected (in each time step) if they have at least $r$ already-infected neighbours. Motivated by its close connections to models from statistical physics, such as the Ising model of ferromagnetism, and kinetically constrained spin models of the liquid-glass transition, the most extensively-studied case is the two-neighbour bootstrap process on the two-dimensional grid $[n]^2$. Around 15 years ago, in a major ...

Find SimilarView on arXiv

The time of bootstrap percolation for dense initial sets

May 17, 2012

90% Match
Béla Bollobás, Cecilia Holmgren, ... , Uzzell Andrew J.
Combinatorics
Probability

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

Find SimilarView on arXiv

Sharp Metastability Threshold for Two-Dimensional Bootstrap Percolation

June 12, 2002

89% Match
Alexander E. Holroyd
Probability
Mathematical Physics

In the bootstrap percolation model, sites in an $L$ by $L$ square are initially independently declared active with probability $p$. At each time step, an inactive site becomes active if at least two of its four neighbours are active. We study the behaviour as $p \to 0$ and $L \to \infty$ simultaneously of the probability $I(L,p)$ that the entire square is eventually active. We prove that $I(L,p) \to 1$ if $\liminf p \log L > \lambda$, and $I(L,p) \to 0$ if $\limsup p \log L <...

Find SimilarView on arXiv

Bootstrap percolation in high dimensions

July 17, 2009

89% Match
Jozsef Balogh, Bela Bollobas, Robert Morris
Probability
Combinatorics

In r-neighbour bootstrap percolation on a graph G, a set of initially infected vertices A \subset V(G) is chosen independently at random, with density p, and new vertices are subsequently infected if they have at least r infected neighbours. The set A is said to percolate if eventually all vertices are infected. Our aim is to understand this process on the grid, [n]^d, for arbitrary functions n = n(t), d = d(t) and r = r(t), as t -> infinity. The main question is to determine...

Find SimilarView on arXiv

The time of bootstrap percolation in two dimensions

May 23, 2013

89% Match
Paul Balister, Béla Bollobás, Paul Smith
Probability
Combinatorics

We study the distribution of the percolation time $T$ of two-neighbour bootstrap percolation on $[n]^2$ with initial set $A\sim\mathrm{Bin}([n]^2,p)$. We determine $T$ with high probability up to a constant factor for all $p$ above the critical probability for percolation, and to within a $1+o(1)$ factor for a large range of $p$.

Find SimilarView on arXiv

Bootstrap percolation is local

April 11, 2024

88% Match
Ivailo Hartarsky, Augusto Teixeira
Probability
Statistical Mechanics
Combinatorics
Mathematical Physics

Metastability thresholds lie at the heart of bootstrap percolation theory. Yet proving precise lower bounds is notoriously hard. We show that for two of the most classical models, two-neighbour and Frob\"ose, upper bounds are sharp to essentially arbitrary precision, by linking them to their local counterparts. In Frob\"ose bootstrap percolation, iteratively, any vertex of the square lattice that is the only healthy vertex of a $1\times1$ square becomes infected and infecti...

Find SimilarView on arXiv

Nucleation and growth in two dimensions

August 25, 2015

88% Match
Béla Bollobás, Simon Griffiths, Robert Morris, ... , Smith Paul
Probability
Combinatorics

We consider a dynamical process on a graph $G$, in which vertices are infected (randomly) at a rate which depends on the number of their neighbours that are already infected. This model includes bootstrap percolation and first-passage percolation as its extreme points. We give a precise description of the evolution of this process on the graph $\mathbb{Z}^2$, significantly sharpening results of Dehghanpour and Schonmann. In particular, we determine the typical infection time ...

Find SimilarView on arXiv

An Improved Upper Bound for Bootstrap Percolation in All Dimensions

April 14, 2012

88% Match
Andrew J. Uzzell
Combinatorics
Probability

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\'...

Find SimilarView on arXiv