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

Given two graphs $G$ and $H$, it is said that $G$ percolates in $H$-bootstrap process if one could join all the nonadjacent pairs of vertices of $G$ in some order such that a new copy of $H$ is created at each step. Balogh, Bollob\'as and Morris in 2012 investigated the threshold of $H$-bootstrap percolation in the Erd\H{o}s-R\'enyi model for the complete graph $H$ and proposed the similar problem for $H=K_{s,t}$, the complete bipartite graph. In this paper, we provide lower ...

Given a graph $G$ and assuming that some vertices of $G$ are infected, the $r$-neighbor bootstrap percolation rule makes an uninfected vertex $v$ infected if $v$ has at least $r$ infected neighbors. The $r$-percolation number, $m(G,r)$, of $G$ is the minimum cardinality of a set of initially infected vertices in $G$ such that after continuously performing the $r$-neighbor bootstrap percolation rule each vertex of $G$ eventually becomes infected. In this paper, we consider per...

Majority bootstrap percolation on a graph $G$ is an epidemic process defined in the following manner. Firstly, an initially infected set of vertices is selected. Then step by step the vertices that have more infected than non-infected neighbours are infected. We say that percolation occurs if eventually all vertices in $G$ become infected. In this paper we study majority bootstrap percolation on the Erd\H{o}s-R\'enyi random graph $G(n,p)$ above the connectivity threshold. P...

Inspired by the works of Goldreich and Ron (J. ACM, 2017) and Nakar and Ron (ICALP, 2021), we initiate the study of property testing in dynamic environments with arbitrary topologies. Our focus is on the simplest non-trivial rule that can be tested, which corresponds to the 1-BP rule of bootstrap percolation and models a simple spreading behavior: Every "infected" node stays infected forever, and each "healthy" node becomes infected if and only if it has at least one infected...

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

For $r\geq1$, the $r$-neighbour bootstrap process in a graph $G$ starts with a set of infected vertices and, in each time step, every vertex with at least $r$ infected neighbours becomes infected. The initial infection percolates if every vertex of $G$ is eventually infected. We exactly determine the minimum cardinality of a set that percolates for the $3$-neighbour bootstrap process when $G$ is a $3$-dimensional grid with minimum side-length at least $11$. We also characteri...

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

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

The $r$-neighbor bootstrap percolation is a graph infection process based on the update rule by which a vertex with $r$ infected neighbors becomes infected. We say that an initial set of infected vertices propagates if all vertices of a graph $G$ are eventually infected, and the minimum cardinality of such a set in $G$ is called the $r$-bootstrap percolation number, $m(G,r)$, of $G$. In this paper, we study percolating sets in direct products of graphs. While in general graph...

We show that for every $r\ge 3$, the maximal running time of the $K^{r}_{r+1}$-bootstrap percolation in the complete $r$-uniform hypergraph on $n$ vertices $K_n^r$ is $\Theta(n^r)$. This answers a recent question of Noel and Ranganathan in the affirmative, and disproves a conjecture of theirs. Moreover, we show that the prefactor is of the form $r^{-r} \mathrm{e}^{O(r)}$ as $r\to\infty$.