ID: 0806.4485

Bootstrap percolation in three dimensions

June 27, 2008

View on ArXiv

Similar papers 2

Three-dimensional 2-critical bootstrap percolation: The stable sets approach

January 27, 2022

89% Match
Daniel Blanquicett
Probability

Consider a $p$-random subset $A$ of initially infected vertices in the discrete cube $[L]^3$, and assume that the neighbourhood of each vertex consists of the $a_i$ nearest neighbours in the $\pm e_i$-directions for each $i \in \{1,2,3\}$, where $a_1\le a_2\le a_3$. Suppose we infect any healthy vertex $v\in [L]^3$ already having $r$ infected neighbours, and that infected sites remain infected forever. In this paper we determine $\log$ of the critical length for percolation u...

Find SimilarView on arXiv

The time of bootstrap percolation with dense initial sets for all thresholds

September 19, 2012

89% Match
Béla Bollobás, Paul Smith, Andrew J. Uzzell
Probability
Combinatorics

We study the percolation time of the $r$-neighbour bootstrap percolation model on the discrete torus $(\Z/n\Z)^d$. For $t$ at most a polylog function of $n$ and initial infection probabilities within certain ranges depending on $t$, we prove that the percolation time of a random subset of the torus is exactly equal to $t$ with high probability as $n$ tends to infinity. Our proof rests crucially on three new extremal theorems that together establish an almost complete understa...

Find SimilarView on arXiv

Bootstrap Percolation on Degenerate Graphs

May 23, 2016

89% Match
Marinus Gottschau
Combinatorics

In this paper we focus on $r$-neighbor bootstrap percolation, which is a process on a graph where initially a set $A_0$ of vertices gets infected. Now subsequently, an uninfected vertex becomes infected if it is adjacent to at least $r$ infected vertices. Call $A_f$ the set of vertices that is infected after the process stops. More formally set $A_t:=A_{t-1}\cup \{v\in V: |N(v)\cap A_{t-1}|\geq r\}$, where $N(v)$ is the neighborhood of $v$. Then $A_f=\bigcup_{t>0} A_t$. We de...

Find SimilarView on arXiv

Bootstrap Percolation on the Binomial Random $k$-uniform Hypergraph

March 19, 2024

89% Match
Mihyun Kang, Christoph Koch, Tamás Makai
Probability

We investigate the behaviour of $r$-neighbourhood bootstrap percolation on the binomial $k$-uniform random hypergraph $H_k(n,p)$ for given integers $k\geq 2$ and $r\geq 2$. In $r$-neighbourhood bootstrap percolation, infection spreads through the hypergraph, starting from a set of initially infected vertices, and in each subsequent step of the process every vertex with at least $r$ infected neighbours becomes infected. For our analysis the set of initially infected vertices i...

Find SimilarView on arXiv

Anisotropic bootstrap percolation in three dimensions

August 30, 2019

89% Match
Daniel Blanquicett
Probability

Consider a $p$-random subset $A$ of initially infected vertices in the discrete cube $[L]^3$, and assume that the neighbourhood of each vertex consists of the $a_i$ nearest neighbours in the $\pm e_i$-directions for each $i \in \{1,2,3\}$, where $a_1\le a_2\le a_3$. Suppose we infect any healthy vertex $x\in [L]^3$ already having $a_3+1$ infected neighbours, and that infected sites remain infected forever. In this paper we determine the critical length for percolation up to a...

Find SimilarView on arXiv

Finite size scaling in three-dimensional bootstrap percolation

December 4, 1998

89% Match
Raphael Cerf, Emilio N. M. Cirillo
Statistical Mechanics

We consider the problem of bootstrap percolation on a three dimensional lattice and we study its finite size scaling behavior. Bootstrap percolation is an example of Cellular Automata defined on the $d$-dimensional lattice $\{1,2,...,L\}^d$ in which each site can be empty or occupied by a single particle; in the starting configuration each site is occupied with probability $p$, occupied sites remain occupied for ever, while empty sites are occupied by a particle if at least $...

Find SimilarView on arXiv

The time of graph bootstrap percolation

March 4, 2015

89% Match
Karen Gunderson, Sebastian Koch, Michał Przykucki
Probability
Combinatorics

Graph bootstrap percolation, introduced by Bollob\'as in 1968, is a cellular automaton defined as follows. Given a "small" graph $H$ and a "large" graph $G = G_0 \subseteq K_n$, in consecutive steps we obtain $G_{t+1}$ from $G_t$ by adding to it all new edges $e$ such that $G_t \cup e$ contains a new copy of $H$. We say that $G$ percolates if for some $t \geq 0$, we have $G_t = K_n$. For $H = K_r$, the question about the size of the smallest percolating graphs was independe...

Find SimilarView on arXiv

A sharper threshold for bootstrap percolation in two dimensions

February 20, 2010

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

Maximal Bootstrap Percolation Time on the Hypercube via Generalised Snake-in-the-Box

July 28, 2017

88% Match
Ivailo Hartarsky
Combinatorics

In $r$-neighbour bootstrap percolation, vertices (sites) of a graph $G$ are infected, round-by-round, if they have $r$ neighbours already infected. Once infected, they remain infected. An initial set of infected sites is said to percolate if every site is eventually infected. We determine the maximal percolation time for $r$-neighbour bootstrap percolation on the hypercube for all $r \geq 3$ as the dimension $d$ goes to infinity up to a logarithmic factor. Surprisingly, it tu...

Find SimilarView on arXiv