Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPolluted Bootstrap Percolation in Three Dimensions
106
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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,qto 0$. We show that this density converges to $1$ if $q ll p^3(log p^{-1})^{-3}$ for both standard and modified rules. Our principal result is a complementary bound with a matching power for the modified model: there exists $C$ such that the final density converges to $0$ if $q > Cp^3$. For the standard model, we establish convergence to $0$ under the stronger condition $q>Cp^2$.
rate research
Read More
By bootstrap percolation we mean the following deterministic process on a graph $G$. Given a set $A$ of vertices infected at time 0, new vertices are subsequently infected, at each time step, if they have at least $rinmathbb{N}$ previously infected neighbors. When the set $A$ is chosen at random, the main aim is to determine the critical probability $p_c(G,r)$ at which percolation (infection of the entire graph) becomes likely to occur. This bootstrap process has been extensively studied on the $d$-dimensional grid $[n]^d$: with $2leq rleq d$ fixed, it was proved by Cerf and Cirillo (for $d=r=3$), and by Cerf and Manzo (in general), that [p_c([n]^d,r)=Thetabiggl(frac{1}{log_{(r-1)}n}biggr)^{d-r+1},] where $log_{(r)}$ is an $r$-times iterated logarithm. However, the exact threshold function is only known in the case $d=r=2$, where it was shown by Holroyd to be $(1+o(1))frac{pi^2}{18log n}$. In this paper we shall determine the exact threshold in the crucial case $d=r=3$, and lay the groundwork for solving the problem for all fixed $d$ and $r$.
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 independently with probability p > 0, we provide a law of large numbers for the number of vertices that will have been infected by the end of the process. We also focus on a special case of such random graphs which exhibit a power-law degree distribution with exponent in (2,3). The first two authors have shown the existence of a critical function a_c(n) such that a_c(n)=o(n) with the following property. Let n be the number of vertices of the underlying random graph and let a(n) be the number of the vertices that are initially infected. Assume that a set of a(n) vertices is chosen randomly and becomes externally infected. If a(n) << a_c(n), then the process does not evolve at all, with high probability as n grows, whereas if a(n)>> a_c(n), then with high probability the final set of infected vertices is linear. Using the techniques of the previous theorem, we give the precise asymptotic fraction of vertices which will be eventually infected when a(n) >> a_c (n) but a(n) = o(n). Note that this corresponds to the case where p approaches 0.
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 $rgeq 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 the underlying graph is an inhomogeneous random graph, which exhibits a power-law degree distribution, and initially there are $a(n)$ randomly infected nodes. The main focus of this paper is the number of vertices that will have been infected by the end of the process. The main result of this work is that if the degree sequence of the random graph follows a power law with exponent $beta$, where $2 < beta < 3$, then a sublinear number of initially infected vertices is enough to spread the infection over a linear fraction of the nodes of the random graph, with high probability. More specifically, we determine explicitly a critical function $a_c(n)$ such that $a_c(n)=o(n)$ with the following property. Assuming that $n$ is the number of vertices of the underlying random graph, if $a(n) ll a_c(n)$, then the process does not evolve at all, with high probability as $n$ grows, whereas if $a(n)gg a_c(n)$, then there is a constant $eps>0$ such that, with high probability, the final set of infected vertices has size at least $eps n$. It turns out that when the maximum degree is $o(n^{1/(beta -1)})$, then $a_c(n)$ depends also on $r$. But when the maximum degree is $Theta (n^{1/(beta -1)})$, then $a_c (n)=n^{beta -2 over beta -1}$.
We study directed rigidity percolation (equivalent to directed bootstrap percolation) on three different lattices: square, triangular, and augmented triangular. The first two of these display a first-order transition at p=1, while the augmented triangular lattice shows a continuous transition at a non-trivial p_c. On the augmented triangular lattice we find, by extensive numerical simulation, that the directed rigidity percolation transition belongs to the same universality class as directed percolation. The same conclusion is reached by studying its surface critical behavior, i.e. the spreading of rigidity from finite clusters close to a non-rigid wall. Near the discontinuous transition at p=1 on the triangular lattice, we are able to calculate the finite-size behavior of the density of rigid sites analytically. Our results are confirmed by numerical simulation.
Bootstrap percolation is an often used model to study the spread of diseases, rumors, and information on sparse random graphs. The percolation process demonstrates a critical value such that the graph is either almost completely affected or almost completely unaffected based on the initial seed being larger or smaller than the critical value. To analyze intervention strategies we provide the first analytic determination of the critical value for basic bootstrap percolation in random graphs when the vertex thresholds are nonuniform and provide an efficient algorithm. This result also helps solve the problem of Percolation with Coinflips when the infection process is not deterministic, which has been a criticism about the model. We also extend the results to clustered random graphs thereby extending the classes of graphs considered. In these graphs the vertices are grouped in a small number of clusters, the clusters model a fixed communication network and the edge probability is dependent if the vertices are in close or far clusters. We present simulations for both basic percolation and interventions that support our theoretical results.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
