ID: 0806.4485

Bootstrap percolation in three dimensions

June 27, 2008

View on ArXiv

Similar papers 3

Bootstrap percolation in inhomogeneous random graphs

February 11, 2014

88% Match
Hamed Amini, Nikolaos Fountoulakis, Konstantinos Panagiotou
Probability
Combinatorics

A bootstrap percolation process on a graph G is an "infection" process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round every uninfected node which has at least r infected neighbours becomes infected and remains so forever. The parameter r > 1 is fixed. We consider this process in the case where the underlying graph is an inhomogeneous random graph whose kernel is of rank 1. Assuming that initially every vertex is infected...

Find SimilarView on arXiv

Majority bootstrap percolation on the hypercube

February 13, 2007

88% Match
József Balogh, Béla Bollobás, Robert Morris
Combinatorics
Probability

In majority bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: if at least half of the neighbours of a vertex v are already infected, then v is also infected, and infected vertices remain infected forever. Percolation occurs if eventually every vertex is infected. The elements of the set of initially infected vertices, A \subset V(G), are normally chosen independently at random, each with probability p, say. This process ...

Find SimilarView on arXiv

Polluted Bootstrap Percolation with Threshold Two in All Dimensions

May 4, 2017

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

In the polluted bootstrap percolation model, the vertices of a graph are independently declared initially occupied with probability p or closed with probability q. At subsequent steps, a vertex becomes occupied if it is not closed and it has at least r occupied neighbors. On the cubic lattice Z^d of dimension d>=3 with threshold r=2, we prove that the final density of occupied sites converges to 1 as p and q both approach 0, regardless of their relative scaling. Our result pa...

Find SimilarView on arXiv

Bootstrap percolation on the high-dimensional Hamming graph

June 19, 2024

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

A sharp threshold for a modified bootstrap percolation with recovery

May 29, 2015

88% Match
Tom Coker, Karen Gunderson
Probability
Combinatorics

Bootstrap percolation is a type of cellular automaton on graphs, introduced as a simple model of the dynamics of ferromagnetism. Vertices in a graph can be in one of two states: `healthy' or `infected' and from an initial configuration of states, healthy vertices become infected by local rules. While the usual bootstrap processes are monotone in the sets of infected vertices, in this paper, a modification is examined in which infected vertices can return to a healthy state. V...

Find SimilarView on arXiv

Deterministic bootstrap percolation in high dimensional grids

August 30, 2013

88% 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 in power-law random graphs

November 5, 2011

88% Match
Hamed Amini, Nikolaos Fountoulakis
Probability
Statistical Mechanics
Combinatorics

A bootstrap percolation process on a graph $G$ is an "infection" process which evolves in rounds. Initially, there is a subset of infected nodes and in each subsequent round each uninfected node which has at least $r$ infected neighbours becomes infected and remains so forever. The parameter $r\geq 2$ is fixed. Such processes have been used as models for the spread of ideas or trends within a network of individuals. We analyse bootstrap percolation process in the case where...

Find SimilarView on arXiv

Bootstrap percolation on G(n,p) revisited

May 10, 2016

88% Match
Mihyun Kang, Tamás Makai
Combinatorics

Bootstrap percolation on a graph with infection threshold $r\in \mathbb{N}$ is an infection process, which starts from a set of initially infected vertices and in each step every vertex with at least $r$ infected neighbours becomes infected. We consider bootstrap percolation on the binomial random graph $G(n,p)$, which was investigated among others by Janson, \L uczak, Turova and Valier (2012). We improve their results by strengthening the probability bounds for the number of...

Find SimilarView on arXiv

Minimum degree conditions for small percolating sets in bootstrap percolation

March 31, 2017

88% Match
Karen Gunderson
Combinatorics

The $r$-neighbour bootstrap process is an update rule for the states of vertices in which `uninfected' vertices with at least $r$ `infected' neighbours become infected and a set of initially infected vertices is said to \emph{percolate} if eventually all vertices are infected. For every $r \geq 3$, a sharp condition is given for the minimum degree of a sufficiently large graph that guarantees the existence of a percolating set of size $r$. In the case $r=3$, for $n$ large eno...

Find SimilarView on arXiv

Polluted Bootstrap Percolation in Three Dimensions

June 22, 2017

87% Match
Janko Gravner, Alexander E. Holroyd, David Sivakoff
Probability

In the polluted bootstrap percolation model, vertices of the cubic lattice $\mathbb{Z}^3$ are independently declared initially occupied with probability $p$ or closed with probability $q$. Under the standard (respectively, modified) bootstrap rule, a vertex becomes occupied at a subsequent step if it is not closed and it has at least $3$ occupied neighbors (respectively, an occupied neighbor in each coordinate). We study the final density of occupied vertices as $p,q\to 0$. W...

Find SimilarView on arXiv