ID: 2209.07594

Extremal Bounds for Three-Neighbour Bootstrap Percolation in Dimensions Two and Three

September 15, 2022

View on ArXiv

Similar papers 2

Bootstrap percolation in high dimensions

July 17, 2009

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

Anisotropic bootstrap percolation in three dimensions

August 30, 2019

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

The maximum time of 2-neighbour bootstrap percolation in grid graphs and some parameterized results

August 27, 2015

86% Match
Thiago Braga Marcilon, Rudini Menezes Sampaio
Computational Complexity

In 2-neighborhood bootstrap percolation on a graph $G$, an infection spreads according to the following deterministic rule: infected vertices of $G$ remain infected forever and in consecutive rounds healthy vertices with at least two already infected neighbors become infected. Percolation occurs if eventually every vertex is infected. The maximum time $t(G)$ is the maximum number of rounds needed to eventually infect the entire vertex set. In 2013, it was proved by Benevides ...

Find SimilarView on arXiv

Bootstrap Percolation on Degenerate Graphs

May 23, 2016

86% 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, Connectivity, and Graph Distance

September 22, 2023

86% Match
Hudson LaFayette, Rayan Ibrahim, Kevin McCall
Combinatorics

Bootstrap Percolation is a process defined on a graph which begins with an initial set of infected vertices. In each subsequent round, an uninfected vertex becomes infected if it is adjacent to at least $r$ previously infected vertices. If an initially infected set of vertices, $A_0$, begins a process in which every vertex of the graph eventually becomes infected, then we say that $A_0$ percolates. In this paper we investigate bootstrap percolation as it relates to graph dist...

Find SimilarView on arXiv

A sharp threshold for a modified bootstrap percolation with recovery

May 29, 2015

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

The $d$-dimensional bootstrap percolation models with threshold at least double exponential

January 22, 2022

85% Match
Daniel Blanquicett
Probability

Consider a $p$-random subset $A$ of initially infected vertices in the discrete cube $[L]^d$, 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,\dots, d\}$, where $a_1\le a_2\le \dots \le a_d$. Suppose we infect any healthy vertex $v\in [L]^d$ already having $r$ infected neighbours, and that infected sites remain infected forever. In this paper we determine the $(d-1)$-times iterated log...

Find SimilarView on arXiv

Universal behaviour of majority bootstrap percolation on high-dimensional geometric graphs

June 25, 2024

85% Match
Maurício Collares, Joshua Erde, ... , Kang Mihyun
Combinatorics
Probability

Majority bootstrap percolation is a monotone cellular automata that can be thought of as a model of infection spreading in networks. Starting with an initially infected set, new vertices become infected once more than half of their neighbours are infected. The average case behaviour of this process was studied on the $n$-dimensional hypercube by Balogh, Bollob\'{a}s and Morris, who showed that there is a phase transition as the typical density of the initially infected set in...

Find SimilarView on arXiv

Line percolation

March 26, 2014

85% Match
Paul Balister, Béla Bollobás, ... , Narayanan Bhargav
Probability
Combinatorics

We study a new geometric bootstrap percolation model, line percolation, on the $d$-dimensional integer grid $[n]^d$. In line percolation with infection parameter $r$, infection spreads from a subset $A\subset [n]^d$ of initially infected lattice points as follows: if there exists an axis-parallel line $L$ with $r$ or more infected lattice points on it, then every lattice point of $[n]^d$ on $L$ gets infected, and we repeat this until the infection can no longer spread. The el...

Find SimilarView on arXiv

The maximum time of 2-neighbor bootstrap percolation: complexity results

August 27, 2015

85% Match
Thiago Braga Marcilon, Rudini Menezes Sampaio
Computational Complexity

In 2-neighborhood bootstrap percolation on a graph G, an infection spreads according to the following deterministic rule: infected vertices of G remain infected forever and in consecutive rounds healthy vertices with at least 2 already infected neighbors become infected. Percolation occurs if eventually every vertex is infected. The maximum time t(G) is the maximum number of rounds needed to eventually infect the entire vertex set. In 2013, it was proved \cite{eurocomb13} tha...

Find SimilarView on arXiv