Nucleation and growth in two dimensions

The theme of this paper is the analysis of bootstrap percolation processes on random graphs generated by preferential attachment. This is a class of infection processes where vertices have two states: they are either infected or susceptible. At each round every susceptible vertex which has at least $r\geq 2$ infected neighbours becomes infected and remains so forever. Assume that initially $a(t)$ vertices are randomly infected, where $t$ is the total number of vertices of the...

Bootstrap percolation is a well-known activation process in a graph, in which a node becomes active when it has at least $r$ active neighbors. Such process, originally studied on regular structures, has been recently investigated also in the context of random graphs, where it can serve as a simple model for a wide variety of cascades, such as the spreading of ideas, trends, viral contents, etc. over large social networks. In particular, it has been shown that in $G(n,p)$ the ...

We introduce a class of cellular automata growth models on the two-dimensional integer lattice with finite cross neighborhoods. These dynamics are determined by a Young diagram $\mathcal Z$ and the radius $\rho$ of the neighborhood, which we assume to be sufficiently large. A point becomes occupied if the pair of counts of currently occupied points on the horizontal and vertical parts of the neighborhood lies outside $\mathcal Z$. Starting with a small density $p$ of occupied...

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

Bootstrap percolation is a process that is used to model the spread of an infection on a given graph. In the model considered here each vertex is equipped with an individual threshold. As soon as the number of infected neighbors exceeds that threshold, the vertex gets infected as well and remains so forever. We perform a thorough analysis of bootstrap percolation on a novel model of directed and inhomogeneous random graphs, where the distribution of the edges is specified by ...

We introduce a new percolation model to describe and analyze the spread of an epidemic on a general directed and locally finite graph. We assign a two-dimensional random weight vector to each vertex of the graph in such a way that the weights of different vertices are i.i.d., but the two entries of the vector assigned to a vertex need not be independent. The probability for an edge to be open depends on the weights of its end vertices, but conditionally on the weights, the st...

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

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

We consider bootstrap percolation and diffusion in sparse random graphs with fixed degrees, constructed by configuration model. Every node has two states: it is either active or inactive. We assume that to each node is assigned a nonnegative (integer) threshold. The diffusion process is initiated by a subset of nodes with threshold zero which consists of initially activated nodes, whereas every other node is inactive. Subsequently, in each round, if an inactive node with thre...

Bootstrap percolation in (random) graphs is a contagion dynamics among a set of vertices with certain threshold levels. The process is started by a set of initially infected vertices, and an initially uninfected vertex with threshold $k$ gets infected as soon as the number of its infected neighbors exceeds $k$. This process has been studied extensively in so called \textit{rank one} models. These models can generate random graphs with heavy-tailed degree sequences but they ar...