ID: 1305.5444

The time of bootstrap percolation in two dimensions

May 23, 2013

View on ArXiv
Paul Balister, Béla Bollobás, Paul Smith
Mathematics
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$.

Similar papers 1

The time of bootstrap percolation for dense initial sets

May 17, 2012

89% 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

Sensitive bootstrap percolation second term

March 27, 2023

89% Match
Ivailo Hartarsky
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 ne...

Find SimilarView on arXiv
Fabricio Benevides, Michał Przykucki
Combinatorics

We consider a classic model known as bootstrap percolation on the $n \times n$ square grid. To each vertex of the grid we assign an initial state, infected or healthy, and then in consecutive rounds we infect every healthy vertex that has at least $2$ already infected neighbours. We say that percolation occurs if the whole grid is eventually infected. In this paper, contributing to a recent series of extremal results in this field, we prove that the maximum time a bootstrap p...

Noise sensitivity in bootstrap percolation

September 28, 2015

88% Match
Zsolt Bartha, Gábor Pete
Probability
Combinatorics

Answering questions of Itai Benjamini, we show that the event of complete occupation in 2-neighbour bootstrap percolation on the d-dimensional box [n]^d, for d\geq 2, at its critical initial density p_c(n), is noise sensitive, while in k-neighbour bootstrap percolation on the d-regular random graph G_{n,d}, for 2\leq k\leq d-2, it is insensitive. Many open problems remain.

Find SimilarView on arXiv

Bootstrap percolation in high dimensions

July 17, 2009

88% 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 second term for two-neighbour bootstrap percolation in two dimensions

June 23, 2018

88% 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

Smallest percolating sets in bootstrap percolation on grids

July 3, 2019

87% Match
Michał Przykucki, Thomas Shelton
Combinatorics

In this paper we fill in a fundamental gap in the extremal bootstrap percolation literature, by providing the first proof of the fact that for all $d \geq 1$, the size of the smallest percolating sets in $d$-neighbour bootstrap percolation on $[n]^d$, the $d$-dimensional grid of size $n$, is $n^{d-1}$. Additionally, we prove that such sets percolate in time at most $c_d n^2$, for some constant $c_d >0 $ depending on $d$ only.

Find SimilarView on arXiv

A sharper threshold for bootstrap percolation in two dimensions

February 20, 2010

87% 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

Deterministic bootstrap percolation in high dimensional grids

August 30, 2013

87% Match
Hao Huang, Choongbum Lee
Combinatorics

In this paper, we study the k-neighbor bootstrap percolation process on the d-dimensional grid [n]^d, and show that the minimum number of initial vertices that percolate is (1-d/k)n^d + O(n^{d-1})$ when d<=k<=2d. This confirms a conjecture of Pete.

Find SimilarView on arXiv

Bootstrap percolation on the high-dimensional Hamming graph

June 19, 2024

87% Match
Mihyun Kang, Michael Missethan, Dominik Schmid
Combinatorics
Probability

In the random $r$-neighbour bootstrap percolation process on a graph $G$, a set of initially infected vertices is chosen at random by retaining each vertex of $G$ independently with probability $p\in (0,1)$, and "healthy" vertices get infected in subsequent rounds if they have at least $r$ infected neighbours. A graph $G$ \emph{percolates} if every vertex becomes eventually infected. A central problem in this process is to determine the critical probability $p_c(G,r)$, at whi...

Find SimilarView on arXiv