Abstract
We study atypical behavior in bootstrap percolation on the Erdős–Rényi random graph. Initially a set S is infected. Other vertices are infected once at least r of their neighbors become infected. Janson et al. (Ann Appl Probab 22(5):1989–2047, 2012) locates the critical size of S, above which it is likely that the infection will spread almost everywhere. Below this threshold, a central limit theorem is proved for the size of the eventually infected set. In this work, we calculate the rate function for the event that a small set S eventually infects an unexpected number of vertices, and identify the least-cost trajectory realizing such a large deviation.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
Bootstrap percolation was originally proposed by physicists [12, 29] to model the phase transition observed in disordered magnets. Since then a large literature has developed, motivated by beautiful results, e.g. [8, 10, 22, 31], and a variety of applications across many fields, see e.g. [1, 2] and references therein.
In this work, we consider the spread of an infection by the r-neighbor bootstrap percolation dynamics on the Erdős–Rényi [15] graph \({\mathscr {G}}_{n,p}\), in which any two vertices in [n] are neighbors independently with probability p. Although we focus on this special case, we think our methods could be useful in studying the large deviations of any Markovian growth or exploration process. For instance, we have more recently used these methods to study the performance of the greedy independent set algorithm on sparse random graphs [26].
In bootstrap percolation, some subset \(S_0\subset [n]\) is initially infected. Other vertices are infected once at least r of their neighbors become infected. Most of the literature has focused on the typical behavior. Of particular interest is the critical size at which point a uniformly random initial set \(S_0\) is likely to infect most of the graph. Less is known about the atypical behavior, such as when a small set \(S_0\) is capable of eventually infecting many more vertices than expected (e.g. influencers or superspreaders in a social network, viral marketing, etc.).
For analytical convenience, we rephrase the dynamics in terms of an exploration process (cf. [23, 30, 32]) in which vertices are infected one at a time. At any given step, vertices are either susceptible, infected or healthy. All susceptible vertices become infected eventually, and then remain infected. When a vertex is infected, some of the currently healthy vertices may become susceptible. The process ends once a stable configuration has been reached in which no vertices are susceptible.
More formally, at each step t, there are sets \(I_t\) and \(S_t\) of infected and susceptible vertices. Vertices in \([n]\setminus (I_t\cup S_t)\) are currently healthy. Initially, \(I_0=\emptyset \). In step \(t\ge 1\), some vertex \(v_t\in S_{t-1}\) is infected. All remaining edges from \(v_t\) are revealed. To obtain \(S_t\) from \(S_{t-1}\), we remove \(v_t\) and add all neighbors of \(v_t\) with exactly \(r-1\) neighbors in \(I_{t-1}\). We then add \(v_t\) to \(I_{t-1}\) to obtain \(I_t\). The process ends at step \(t_*=\min \{t\ge 1:S_t=\emptyset \}\) when no further vertices can be infected. For technical convenience, we set \(|S_t|=0\) for all \(t\ge t_*\). Let \(I_*=I_{t_*}\) denote the eventually infected set. Since one vertex is infected in each step \(t\le t_*\), we have \(|I_t|=t\) and \(|S_t|\ge |S_{t-1}|-1\) for all such t. In particular, \(t_*=|I_*|\). Clearly, \(I_*\) does not depend on the order in which vertices are infected.
Janson et al. [23] (cf. [34]) identifies the critical size of \(S_0\), for all \(r\ge 2\) and
in the case that \(S_0\) is selected uniformly at random. By the symmetry of \({\mathscr {G}}_{n,p}\), this is the same as for a given set \(S_0\) (independent of \({\mathscr {G}}_{n,p}\)) of the same size. More specifically, a sharp threshold is observed. If more than \((1-1/r)\vartheta \) vertices are initially susceptible, then all except o(n) many vertices are eventually infected. Otherwise, the eventually infected set is much smaller, of size \(O(\vartheta )\ll n\).
Theorem 1
([23] Theorem 3.1) Let p be as in (1) and \(\alpha \ge 0\). Put \(\alpha _r=(1-1/r)\alpha \). Suppose that a set \(S_0=S_0(n)\) (independent of \({\mathscr {G}}_{n,p}\)) of size \(|S_0|\sim \alpha _r\vartheta \) is initially susceptible. If \(\alpha >1\), then with high probability \(|I_*|\sim n\). If \(\alpha <1\), then with high probability \(|I_*|\sim \varphi _\alpha \vartheta \), where \(\varphi _\alpha \in [\alpha _r,\alpha ]\) uniquely satisfies
The extreme cases \(p\sim c/n\) and \(p\sim c/n^{1/r}\) are also addressed in [23], where the model behaves differently. We assume (1) throughout this work.
Moreover, in the subcritical case, a central limit theorem is proved in [23] (see Theorem 3.8). In this work, we study large deviations from the typical behavior in the subcritical case \(\alpha <1\).
Definition 2
For \(\beta < \varphi _\alpha \) (resp. \(\beta > \varphi _\alpha \)), let \(P(S_0,\beta )\) denote the tail probability that the initial susceptibility of \(S_0\subset [n]\) in \({\mathscr {G}}_{n,p}\) results in some number \(|I_*|\le \beta \vartheta \) (resp. \(|I_*|\ge \beta \vartheta \)) of eventually infected vertices.
Informally, \(P(S_0,\beta )\) is the probability that the number \(|I_*|\) of eventually infected vertices is at least as atypical as \(\beta \vartheta \).
Theorem 3
Let p be as in (1), \(\alpha \in [0,1)\) and \(\beta \ne \varphi _\alpha \in [\alpha _r,1]\). Suppose that a set \(S_0=S_0(n)\) (independent of \({\mathscr {G}}_{n,p}\)) of size \(|S_0|\sim \alpha _r\vartheta \) is initially susceptible. Then
where
For any given \(\alpha \in [0,1)\), \(\xi (\alpha ,\beta )\) is increasing in \(\beta \in [\alpha _r,\varphi _\alpha )\), decreasing in \(\beta \in (\varphi _\alpha ,1]\) (see Appendix A.2), and \(\xi (\alpha ,\varphi _\alpha )=0\) by (2), in line with Theorem 1. See Fig. 1.
The asymptotically optimal trajectory \(\hat{y}_{\alpha ,\beta }(x)\) for \(|S_{x\vartheta }|/\vartheta \) is given at (9) below (see also Fig. 2). The rate function \(\xi (\alpha ,\beta )\) is found by substituting this into the associated cost function (8). Detailed heuristics are given in Sect. 1.5 below. See Sect. 2 for the proof of Theorem 3.
The point \(\vartheta \) (associated with \(\beta =1\)) is critical. As such, we simply have that \(\xi (\alpha ,\beta )=\xi (\alpha ,1)\) for \(\beta >1\). The reason for this is that the underlying branching process (the Binomial chain \(|S_t|\) discussed in Sects. 1.4 and 1.5 below) governing the dynamics becomes critical upon surviving to time \(t=\vartheta \). Surviving beyond this point, supposing that it has been reached, is no longer exponentially unlikely. In other words, the optimal (asymptotic) trajectory \(\hat{y}(x)\) that \(|S_{x\vartheta }|/\vartheta \) typically follows in order to survive beyond \(x=1\) is equal to \(\hat{y}_{\alpha ,1}(x)\) on [0, 1] (this has cost \(-\xi (\alpha ,1)\)). From then on (\(x>1\)), there is a zero-cost path that \(\hat{y}(x)\) can follow.
We note here that in [23] (see Theorem 3.1) it is shown that \(|I_*|/\vartheta \) converges to the typical value \(\varphi _\alpha \) in probability. By Theorem 3 (and the Borel–Cantelli lemma) it follows that this convergence holds almost surely.
1.1 Related Work
Torrisi et al. [33] established a full large deviations principle in the supercritical case, \(\alpha >1\), where typically \(|I_*|\sim n\). As discussed in [33], the main step in this regard is establishing sharp tail estimates (as in our Theorem 3 above). The full large deviations principle then follows by “elementary topological considerations.” Although we have not pursued it, we suspect that a full large deviations principle also holds in the present subcritical setting.
In closing, let us remark that it might be interesting to investigate the nature of \({\mathscr {G}}_{n,p}\), conditioned on the event that a given \(S_0\) eventually infects a certain number of vertices, or on the existence of such a set \(S_0\).
1.2 Motivation
We came to this problem in studying H-bootstrap percolation on \({\mathscr {G}}_{n,p}\), as introduced by Balogh et al. [11], where all edges in \({\mathscr {G}}_{n,p}\) are initially infected and any other edge in an otherwise infected copy of H becomes infected. In the case that \(H=K_4\), there is a useful connection with the usual r-neighbor bootstrap percolation model when \(r=2\). Theorem 3 (when \(r=2\) and \(\vartheta =\Theta (\log n)\)) plays a role (together with [9, 27]) in locating the critical probability \(p_c\sim 1/\sqrt{3n\log n}\), where it becomes likely that all edges in \(K_n\) are infected eventually. This solves an open problem in [11].
1.3 Contagious Sets
A susceptible set \(S_0\) is called contagious if it infects all of \({\mathscr {G}}_{n,p}\) eventually (i.e., \(I_*=[n]\)). Such sets have been studied for various graphs (e.g. [13, 18, 19, 28]). Recently, Feige et al. [16] considered the \({\mathscr {G}}_{n,p}\) case.
By Theorem 1, \({\mathscr {G}}_{n,p}\) has contagious sets of size \(\Theta (\vartheta )\), however, there exist contagious sets that are much smaller. In [16], upper and lower bounds are obtained for the minimal size \(m({\mathscr {G}}_{n,p},r)\) of a contagious set in \({\mathscr {G}}_{n,p}\). More recently [9], we showed that
is the sharp threshold for contagious sets of the smallest possible size r.
For \(p<p_c\), Theorem 3 yields lower bounds for \(m({\mathscr {G}}_{n,p},r)\) that sharpen those in [16] by a linear, multiplicative factor in r. Of course, finding sets of this size (if they exist) is a difficult and interesting problem (cf. the NP-complete problem of target set selection from viral marketing [14, 25]).
Corollary 4
Suppose that, for some \(1\ll \vartheta \ll n\),
Then, with high probability,
This result follows by an easy union bound, applying Theorem 3 in the case that \(\alpha =0\) and \(\beta =1\), see Appendix A.4.
By [9] this lower bound is sharp for p close to \(p_c\), that is, when \(\vartheta \sim \log n\). The methods in [9] might establish sharpness at least for \(\vartheta \le O(\log {n})\).
1.4 Binomial Chain
As in [23], we study the bootstrap percolation dynamics using the Binomial chain construction based on the work of Scalia-Tomba [30] (cf. Selke [32]). We only state here in this section the properties of this framework that we require, and refer the reader to Sect. 2 of [23] for the details.
Let \(N_t\) be the number of vertices that have become susceptible during some time \(s\in (0,t]\), so that \(|S_t|=N_t-t+|S_0|\). By revealing edges (incident to infected vertices) on a need-to-know basis, the process \(N_t\) can be expressed as the sum of \(n-|S_0|\) independent and identically distributed processes, each of which is 0 until some \(\mathrm{NegBin}(r,p)\) time, and then jumps to 1 (and remains at 1 thereafter). Informally, when a vertex is infected, it gives all of its neighbors a “mark.” A vertex, which was not initially susceptible, is susceptible or infected at a given time if it has received at least r marks by this time. In this way (see [23, 30]), it can be shown that \(|S_t|\) is a Markov process, with
where \(\pi _t=\mathbf{P}(\mathrm{Bin}(t,p)\ge r)\). Moreover, its increments are distributed as
1.5 Heuristics
We first briefly recall the heuristic for Theorem 1 given in Sect. 6 of [23]. By the law of large numbers, with high probability \(|S_t|\approx \mathbf{E}|S_t|\). A calculation shows that if \(|S_0| > (1-1/r)\vartheta \) then \(\mathbf{E}|S_t| > t\) for \(t < n-o(n)\). On the other hand, if \(|S_0|\sim \alpha _r\vartheta \), for some \(\alpha <1\), then we have \(\mathbf{E}|S_{\varphi _\alpha \vartheta }| \approx 0\). To see this, note that \(pt=O[(\vartheta /n)^{1/r}]\ll 1\) for \(t\le O(\vartheta )\) since \(\vartheta \ll n\). Hence (see e.g. Sect. 8 of [23]) we have
and so
Next, we describe a natural heuristic, using the Euler–Lagrange equation, that allows us to anticipate the least-cost, deviating trajectories (the functions \(\hat{y}_{\alpha ,\beta }\) in (9) below), which lead to Theorem 3. The proof, given in Sect. 2 below, makes this rigorous by a discrete analogue of the Euler–Lagrange equation. We think this method will be of use in studying the tail behavior of other random processes.
Consider a trajectory \(y(x)\ge 0\) from \(\alpha _r\) to 0 over \([0,\beta ]\). Suppose that \(|S_{x\vartheta }|/\vartheta \) has followed this trajectory until step \(t-1=x\vartheta \). In the next step t, some vertex \(v_t\in S_{t-1}\) is infected. There are approximately a Poisson with mean \(np^r{t-1\atopwithdelims ()r-1}\approx x^{r-1}\) (this approximation holds by (1) and standard combinatorial estimates) number of vertices that are neighbors with \(v_t\) and \(r-1\) of the \(t-1\) vertices infected in previous steps \(s<t\). Such vertices become susceptible in step t. Therefore, to continue along this trajectory, we require this Poisson random variable to take the value
(The “\(+1\)” accounts for the vertex \(v_t\in S_{t-1}\) that is infected in step t, and so removed from the next susceptible set \(S_t\).) As is well-known, this event has approximate log probability \(-\Gamma ^*_{x^{r-1}}(1+y'(x))\), where
is the Legendre–Fenchel transformation of the cumulant-generating function of a mean \(\lambda \) Poisson. Hence \(|S_{x\vartheta }|/\vartheta \approx y(x)\) on \([0,\beta ]\) with approximate log probability
(cf. (13) below). Maximizing this integral is particularly simple, since the integrand depends on \(y'\), but not y. The Euler–Lagrange equation implies that the least-cost trajectory satisfies
except where possibly the boundary constraint \(y(x)\ge 0\) might intervene.
Since, as noted above, \(|S_t|\ge |S_{t-1}|-1\) for all t, we may assume that \(\beta \ge \alpha _r\). That is, any trajectory y(x) of \(|S_{x\vartheta }|/\vartheta \) decreases no faster than \(-x\). Also note that \((\alpha -\alpha _r)/\alpha ^r=1/(r\alpha ^{r-1})\), and that for any larger \(b>1/(r\alpha ^{r-1})\) the function \(bx^r-x+\alpha _r\) has no zeros in [0, 1].
As it turns out, the least-cost trajectory from \(\alpha _r\) to 0 over \([0,\beta ]\) is
where \(\alpha \wedge \beta =\min \{\alpha ,\beta \}\). Setting \(\beta =\varphi _\alpha \), we recover by (2) the typical, zero-cost trajectory (7). See Fig. 2. Substituting (9) into (8), we obtain \(\vartheta \xi (\alpha ,\beta )\) after some basic calculus (see Appendix A.1 below).
2 Proof of Theorem 3
Before turning to the proof, let us recall Theorem 3 and the definitions involved. We fix some \(\alpha \in [0,1)\) and \(\beta \ne \varphi _\alpha \in [\alpha _r,1]\) (with \(\varphi _\alpha \) as defined at (2)). We assume that \(|S_0|/\vartheta \rightarrow \alpha _r=(1-1/r)\alpha \) as \(n\rightarrow \infty \), where \(S_0=S_0(n)\) is the initially susceptible set. Recall that \(I_*=I_{t_*}\) is the eventually infected set, where \(t_*\) is the first time t that \(|S_t|=0\) (no susceptible vertices). Finally, recall that Theorem 3 identifies the limit of \((1/\vartheta )\log P(S_0,\beta )\), where \(P(S_0,\beta )\) is the tail probability that \(|I_*|\le \beta \vartheta \) if \(\beta <\varphi _\alpha \) or \(|I_*|\ge \beta \vartheta \) if \(\beta >\varphi _\alpha \).
Upper bounds for \(P(S_0,\beta )\) are established in Sect. 2.1 (\(\beta <\varphi _\alpha \)) and Sect. 2.2 (\(\beta >\varphi _\alpha \)) below. The main idea is to use a discrete version of the Euler–Lagrange equation to identify the asymptotically optimal trajectory \(\hat{y}(x)\) of the process \(|S_{x\vartheta }|/\vartheta \) realizing the associated event (\(|I_*|\le \beta \vartheta \) or \(|I_*|\ge \beta \vartheta \) depending on \(\beta \)). It turns out that \(\hat{y} = \hat{y}_{\alpha ,\beta }\) (see (9) above). More specifically, we use the following result, which is a special case of Theorem 5 in Guseinov [20]. See also [3,4,5,6,7, 17, 24] and references therein for earlier related results and background.
Let \(\Delta x_i=x_{i+1}-x_i\) denote the forward difference operator.
Lemma 5
Fix \(a,b\in {\mathbb {R}}\), a function f(u, v) with continuous partial derivatives \(f_u\) and \(f_v\), and evenly spaced points \(x_0\le x_1\le \cdots \le x_m\). Then the maximizer \(\hat{y}\) of
over trajectories with \(y_0=a\) and \(y_m=b\), satisfies \(f_v(x_{i+1},\Delta \hat{y}_i/\Delta x_i)\equiv c\) for some constant c.
The proof of this result amounts to adding a Lagrange multiplier to constrain \(\sum _i\Delta y_i\) and then comparing the derivative to 0. A more general version, more closely resembling the regular Euler–Lagrange equation, appears in [20]. This allows for more complicated functions \(f(x_i,x_{i+1},y_i,y_{i+1},\Delta y_i/\Delta x_i)\) and points \(x_i\) that need not be evenly spaced. The proof is analogous to that of its continuous counterpart, using summation by parts instead of integration by parts, for instance.
Finally, in Sect. 2.3, we establish asymptotically equivalent lower bounds for \(P(S_0,\beta )\) by considering specific trajectories y that are asymptotically equivalent to \(\hat{y}_{\alpha ,\beta }\). This altogether verifies the asymptotic optimality of \(\hat{y}_{\alpha ,\beta }\) and the convergence of \((1/\vartheta )\log P(S_0,\beta )\).
2.1 Upper Bounds When \(\beta <\varphi _\alpha \)
We begin with the simpler case that \(\beta <\varphi _\alpha \). The opposite case \(\beta >\varphi _\alpha \) follows by an elaboration of these arguments (see Sect. 2.2 below). Since \(\beta <\varphi _\alpha \), note that \(P(S_0,\beta )\) is simply the probability that \(|S_{x\vartheta }|=0\) for some \(x\le \beta \), as this occurs if and only if \(|I_*|\le \beta \vartheta \).
To begin, we discretize the unit interval [0, 1] as follows. Let \(m=\lceil \vartheta /(\log \vartheta )^2\rceil \). Consider the points \(x_i = (i/\vartheta )\lceil (\log \vartheta )^2 \rceil \), for \(i=0,1,\ldots ,m\). Note that the points \(x_i\vartheta \) are evenly spaced integers. Also note that \(x_m\sim 1\), since \(\vartheta \gg 1\).
Let \({\mathscr {Y}}_{n}\) denote the set of trajectories \(y_i=|S_{x_i\vartheta }|/\vartheta \) such that
-
(1)
all \(y_i \vartheta \in {\mathbb {Z}}\),
-
(2)
\(y_0\vartheta =|S_0|\),
-
(3)
all \(\Delta y_i/\Delta x_i\ge -1\), and
-
(4)
\(y_i=0\) for all \(x_i\ge \beta \).
Note that we can assume (3) since, as discussed above, \(|S_t|\ge |S_{t-1}|-1\) for all t. Since \(|S_t|\) is Markov,
By (3) and (4) it follows that all \(y_i\le \beta \) for any \(y\in {\mathscr {Y}}_{n}\). Hence \(|{\mathscr {Y}}_{n}|\le \vartheta ^m\). Therefore, taking a union bound,
where \(\hat{y}\) maximizes the product over \(y\in {\mathscr {Y}}_{n}\). Noting that \((m/\vartheta )\log \vartheta \ll 1\), we find altogether that
We now turn to the issue of identifying \(\hat{y}\in {\mathscr {Y}}_{n}\). By (5) it follows that
Hence, using the standard bound \({n\atopwithdelims ()k}\le (en/k)^k\) and \(1-x\le e^{-x}\),
(We have written the upper bound in this way so as to compare with the lower bound at (18) below.)
Before substituting this upper bound into (10), we collect the following technical result. The proof is elementary, though somewhat tedious, see Sect. Appendix A.5 below. Note that by (1), \(1\ll \vartheta \ll 1/p\).
Lemma 6
We have that
Altogether, we find that
Since \(\log x-x\) is increasing for \(x\in (0,1]\) and \(\Delta (x_i^r)/r\le x_{i+1}^{r-1}\Delta x_i\), it follows by (10) that
where
(cf. (8) above) and \(\hat{y}\in {\mathscr {Y}}_n\) maximizes the sum in (13).
In order to apply Lemma 5, we lift the restriction that all \(y_i\vartheta \in {\mathbb {Z}}\), and maximize
over \(y\in {\mathbb {R}}^{m+1}\) with (i) \(y_0=\alpha _r\), (ii) \(\Delta y_i/\Delta x_i\ge -1\) and (iii) \(y_i=0\) for all \(x_i\ge \beta \). By Lemma 5, the maximizer \(\hat{y}=\hat{y}(n)\) satisfies
between any two given points where \(\hat{y}>0\). Since
this implies that \(1+\Delta \hat{y}_i/\Delta x_i=bx_{i+1}^{r-1}\), for some constant b, between any two points \(x_j<x_k\) where \(\hat{y}_i>0\) for \(j<i<k\). On the other hand, if both \(\hat{y}_j=\hat{y}_k=0\), then necessarily \(\hat{y}_i=0\) for \(j<i<k\). By standard results on the Euler approximation of differential equations (see e.g. Theorems 7.3 and 7.5 in Sect. I.7 of [21]), it follows that, on all segments where \(\hat{y}_i>0\), the discrete derivative \(\Delta \hat{y}_i/\Delta x_i\) is within O(1/m) of the function \(bx^{r-1}-1\), for some \(b=b(n)\).
Altogether, in the limit, it suffices to consider trajectories that take the form \((\beta '-\alpha _r)(x/\beta ')^r-x+\alpha _r\) (until they hit 0), for some \(\beta '\in [\alpha _r,\beta ]\), since (as discussed in Sect. 1.5) these are the only functions \(y(x)=bx^r-x+\alpha _r\) for which (i) \(y(0)=\alpha _r\), (ii) \(y'(x)\ge -1\) and (iii) \(y(x)=0\) for some \(x\le \beta \). Hence, by the above considerations, and the continuity of f, we find that
To conclude, we observe, by Appendices A.1 and A.2, that the right hand side equates to
2.2 Upper bounds When \(\beta >\varphi _\alpha \)
The case \(\beta >\varphi _\alpha \) follows by the same method of proof, however, there are two additional technical complications. Specifically, (i) the set of relevant trajectories \({\mathscr {Y}}_{n}\) in this case (defined below) no longer satisfies \(|{\mathscr {Y}}_{n}|\le [O(\vartheta )]^m\), and (ii) to obtain an upper bound for \((1/\vartheta )\log P(S_0,\beta )\), as in (15) above, we need to take a supremum over a more complicated set of trajectories. This latter issue is due in part to the fact that is not a priori clear that the optimal trajectory \(\hat{y}\) should hit 0 before \(x=1\) (that is, that \(\hat{y}\) is one of \(\hat{y}_{\alpha ,\beta }\)). This indeed turns out to be the case, however, even so, \(\hat{y}_{\alpha ,\beta }\) is slightly more complicated (defined piecewise) when \(\beta >\alpha \).
First note that, for \(\beta >\varphi _\alpha \), \(P(S_0,\beta )\) is the probability that \(|S_{x\vartheta }|>0\) for all \(x< \beta \). Therefore, in this case, we take \({\mathscr {Y}}_{n}\) to be the set of \(y_i=|S_{x_i\vartheta }|/\vartheta \) for which
-
(1)
all \(y_i \vartheta \in {\mathbb {Z}}\),
-
(2)
\(y_0\vartheta =|S_0|\),
-
(3)
all \(\Delta y_i/\Delta x_i\ge -1\), and
-
(4)
\(y_i>0\) for all \(x_i<\beta \).
We no longer have that \(|{\mathscr {Y}}_{n}|\le [O(\vartheta )]^m\). However, for \(t\le O(\vartheta )\), by (5) and Chernoff’s bound,
Therefore, for A sufficiently large, the log probability that any \(|S_t|>A\vartheta \) while \(t\le O(\vartheta )\) is less than \(\vartheta \xi (\alpha ,\beta )\). Hence, arguing as the previous section, we find that
where \({\mathscr {Y}}\) is the set of non-negative trajectories y(x) that start at \(y(0)=\alpha _r\) and take the form \(bx^r-x+a\), for some \(b\ge 0\), wherever they are positive. However, it suffices to consider a smaller set than \({\mathscr {Y}}\). Indeed, observe that the maximizer \(\hat{y}\in {\mathscr {Y}}\) is non-increasing. This is intuitive, since the process is sub-critical while the total number of infected vertices remains less than \(\vartheta \). To see this formally, note that (i) the derivative of any trajectory \(bx^r-x+a\) is \(brx^{r-1}-1\le 0\) for any \(x\le 1\) unless \(b>1/r\), and (ii) we have by (14) that
is decreasing in \(b>1/r\). Hence, it suffices to consider trajectories which take the form \((\beta '-\alpha _r)(x/\beta ')^r-x+\alpha _r\) until they hit 0 at some \(\beta '\in [\alpha _r,\alpha ]\), and then, if \(\beta '<\beta \), are 0 thereafter until \(x=\beta \). (Note that, for any \(b>1/(r\alpha ^{r-1})\), the function \(bx^r-x+\alpha _r\) has no zeros and, since \(\alpha <1\), is increasing eventually on [0, 1].) Therefore, by Appendix A.1,
By basic calculus (see Appendix A.3) it can be shown that the right hand side is bounded by \(\xi (\alpha ,\beta )\).
2.3 Lower Bounds
The lower bound is much simpler. As discussed above, it essentially suffices to consider any trajectory \(y(x)\sim \hat{y}_{\alpha ,\beta }(x)\) which contributes to \(P(S_0,\beta )\), and show that the scaled log probability that \(|S_{x\vartheta }|/\vartheta \) follows this trajectory is asymptotic to \(\xi (\alpha ,\beta )\).
Once again, there is some asymmetry in the cases \(\beta <\varphi _\alpha \) and \(\beta >\varphi _\alpha \) due to the definition of \(P(S_0,\beta )\). For \(\beta <\varphi _\alpha \), we note that if, for instance, all \(|S_{x_i\vartheta }|/\vartheta =\tilde{y}_i\), where
then \(|I_*|\le \beta \vartheta \). The indicator present here ensures that \(|S_{x\vartheta }|\) hits 0 by \(x=\beta \). On the other hand, if \(\beta >\varphi _\alpha \), set
Then if all \(|S_{x_i\vartheta }|/\vartheta =\tilde{y}_i\) we have \(|I_*|\ge \beta \vartheta \). The indicator in this case ensures that \(|S_t|>0\) between increments while \(t<\beta \vartheta \).
Next, we show that
since then, by Sect. 2.1 and 2.2, it follows that
as stated in Theorem 3.
To this end, note that by (11) and the standard bounds \({n\atopwithdelims ()k}\ge (n-k)^k/k!\), \(k!\le ek(k/e)^k\) and \((1-x)^n\ge e^{-xn}(1-nx^2)\), it follows that
(cf. (12)). Therefore, in a similar way as for (13) above (however instead using \(\Delta (x_i^r)/r\ge x_{i}^{r-1}\Delta x_i\)), we find that
where f, once again, is as defined at (14). Therefore, by the choice of \(\tilde{y}_i\), it can be seen (using Appendix A.1) that
References
Adler, J.: Bootstrap percolation. Physica A 171, 453–470 (1991)
Adler, J., Lev, U.: Bootstrap percolation: visualizations and applications. Braz. J. Phys. 33, 641–644 (2003)
Agarwal, R., Ahlbrandt, C., Bohner, M., Peterson, A.: Discrete linear Hamiltonian systems: a survey. Dyn. Syst. Appl. 8(3–4), 307–333 (1999)
Ahlbrandt, C.D.: Discrete variational inequalities, general inequalities, 6 (Oberwolfach, : Internat. Ser. Numer. Math., vol. 103. Birkhäuser, Basel 1992, 93–107 (1990)
Ahlbrandt, C.D.: Equivalence of discrete Euler equations and discrete Hamiltonian systems. J. Math. Anal. Appl. 180(2), 498–517 (1993)
Ahlbrandt, C.D., Hooker, J.W.: A variational view of nonoscillation theory for linear differential equations. Differential and integral equations (Iowa City, Iowa, 1983/Argonne, Ill., 1984), Univ. Missouri-Rolla, Rolla, MO, pp. 1–21 (1985)
Ahlbrandt, C.D., Peterson, A.C.: Discrete Hamiltonian systems, Kluwer Texts in the Mathematical Sciences, vol. 16, Kluwer Academic Publishers Group, Dordrecht, Difference equations, continued fractions, and Riccati equations (1996)
Aizenman, M., Lebowitz, J.L.: Metastability effects in bootstrap percolation. J. Phys. A 21(19), 3801–3813 (1988)
Angel, O., Kolesnik, B.: Sharp thresholds for contagious sets in random graphs. Ann. Appl. Probab. 28(2), 1052–1098 (2018)
Balogh, J., Bollobás, B., Duminil-Copin, H., Morris, R.: The sharp threshold for bootstrap percolation in all dimensions. Trans. Am. Math. Soc. 364(5), 2667–2701 (2012)
Balogh, J., Bollobás, B., Morris, R.: Graph bootstrap percolation. Random Struct. Algorithm. 41(4), 413–440 (2012)
Chalupa, J., Leath, P.L., Reich, G.R.: Bootstrap percolation on a Bethe lattice. J. Phys. C 21, L31–L35 (1979)
Coja-Oghlan, A., Feige, U., Krivelevich, M., Reichman, D.: Contagious sets in expanders. In: Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, pp. 1953–1987 (2015)
Domingos, P., Richardson, M.: Mining the network value of customers. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (New York, NY, USA), KDD ’01, Association for Computing Machinery, pp. 57–66 (2001)
Erdős, P., Rényi, A.: On random graphs. I. Publ. Math. Debrecen 6, 290–297 (1959)
Feige, U., Krivelevich, M., Reichman, D.: Contagious sets in random graphs. Ann. Appl. Probab. 27(5), 2675–2697 (2017)
Fort, T.: Finite Differences and Difference Equations in the Real Domain. Clarendon Press, Oxford (1948)
Freund, D., Poloczek, M., Reichman, D.: Contagious sets in dense graphs. Eur. J. Combin. 68, 66–78 (2018)
Guggiola, A., Semerjian, G.: Minimal contagious sets in random regular graphs. J. Stat. Phys. 158(2), 300–358 (2015)
Guseinov, G.-S.: Discrete calculus of variations, Global analysis and applied mathematics. In: AIP Conf. Proc., vol. 729, Amer. Inst. Phys., Melville, NY, pp. 170–176 (2004)
Hairer, E., Nørsett, S.P., Wanner, G.: Solving Ordinary Differential Equations. I, 2nd ed., Springer Series in Computational Mathematics, vol. 8. Springer, Berlin, Nonstiff problems (1993)
Holroyd, A.E.: Sharp metastability threshold for two-dimensional bootstrap percolation. Probab. Theory Relat. Fields 125(2), 195–224 (2003)
Janson, S., Łuczak, T., Turova, T., Vallier, T.: Bootstrap percolation on the random graph \(G_{n, p}\). Ann. Appl. Probab. 22(5), 1989–2047 (2012)
Kelley, W.G., Peterson, A.C.: Difference Equations, 2nd ed. An Introduction with Applications. Harcourt/Academic Press, San Diego (2001)
Kempe, J., Kleinberg, D., Tardos, É.: Maximizing the spread of influence through a social network. Theory Comput. 11, 105–147 (2015)
Kolesnik, B.: Large deviations of the greedy independent set algorithm on sparse random graphs. Random Struct. Algorithms. arXiv:2011.04613
Kolesnik, B.: The sharp \(K_4\)-percolation threshold on the Erdös–Rényi random graph. Electron. J. Probab. arXiv:1705.08882
Morris, R.: Minimal percolating sets in bootstrap percolation. Electron. J. Combin. 16(1), Research Paper 2, 20 (2009)
Pollak, M., Riess, I.: Application of percolation theory to 2d–3d Heisenberg ferromagnets. Physica Status Solidi (b) 69(1), K15–K18 (1975)
Scalia-Tomba, G.-P.: Asymptotic final-size distribution for some chain-binomial processes. Adv. Appl. Probab. 17(3), 477–495 (1985)
Schonmann, R.H.: On the behavior of some cellular automata related to bootstrap percolation. Ann. Probab. 20(1), 174–193 (1992)
Sellke, T.: On the asymptotic distribution of the size of a stochastic epidemic. J. Appl. Probab. 20(2), 390–394 (1983)
Torrisi, G.L., Garetto, M., Leonardi, E.: A large deviation approach to super-critical bootstrap percolation on the random graph \(G_{n, p}\). Stoch. Process. Appl. 129(6), 1873–1902 (2019)
Vallier, T.: Random graph models and their applications, Ph.D. thesis, Lund University (2007)
Acknowledgements
Omer Angel and Brett Kolesnik would both like to acknowledge the support of NSERC of Canada.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Giulio Biroli.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix A: Technical Results
Appendix A: Technical Results
This section contains several technical results, all of which follow by elementary methods.
1.1 A.1: Rate Function \(\xi \)
We show that
where \(\hat{y}_{\alpha ,\beta }\) and f are as in (9) and (14) above (that is, the cost of the least-cost trajectory \(\hat{y}_{\alpha ,\beta }(x)\) over \([0,\beta ]\) is \(-\xi (\alpha ,\beta )\)).
First note that, whenever \(y_{\alpha ,\beta }(x)>0\),
in which case
Hence, if \(\beta \le \alpha \),
On the other hand, note that
and so
Therefore, if \(\beta >\alpha \), then we find (after some algebraic simplifications) that
1.2 A.2: Shape of \(\xi \)
We note here that \(\xi (\alpha ,\beta )\) is increasing in \(\beta \in [\alpha _r,\varphi _\alpha )\) and decreasing in \(\beta \in (\varphi _\alpha ,1]\) (as in Fig. 1 above). When \(\beta \le \alpha \),
Therefore, if \(\beta \in [\alpha _r,\varphi _\alpha ]\), by (2) and \(\log x\ge 1-1/x\),
On the other hand, if \(\beta \in [\varphi _\alpha ,\alpha ]\), by (2) and \(\log x\le x-1\),
Finally, if \(\beta \in [\alpha ,1]\), note that
1.3 A.3: An Inequality Involving \(\xi \)
We show that, for any \(\beta >\varphi _\alpha \) and \(\beta '\in [\alpha _r,\alpha ]\),
If \(\beta '\ge \beta \) the result is immediate, since by Appendix A.2 we have \(\xi (\alpha ,\beta ')\le \xi (\alpha ,\beta )\) in this case. Hence, assuming that \(\beta <\beta '\), we show that
If \(\beta >\alpha \), then
so we may further assume that \(\beta \le \alpha \). As has already been noted above, \(f(x,0)=1-x^{r-1}+(r-1)\log x\), and so
Hence by (3) it suffices to show that
is increasing in \(x\ge \alpha _r\). Differentiating the above expression with respect to x, we obtain (after some straightforward simplifications)
yielding the claim.
1.4 A.4: Lower Bound for \(m({\mathscr {G}}_{n,p},r)\)
Proof of Theorem 4
For \(\delta >0\), let \(t_\delta =(1-\delta )r\vartheta /\log (n/\vartheta )\). We show that, with high probability, \({\mathscr {G}}_{n,p}\) has no contagious sets smaller than \(t_\delta \). Note that
The expected number of subsets \(S_0\subset [n]\) of size \(|S_0|=t_\delta \) which if initially susceptible cause \(|I_*|\ge \vartheta /(1-1/r)^2\) vertices to be infected eventually is at most
where
Since
\(\psi >0\) for all large n, and the result follows. \(\square \)
1.5 A.5: Increments of \(\pi \)
Proof of Lemma 6
Recall that
When \(i=0\), we have \(\Delta \pi (x_i\vartheta )=\pi (x_1\vartheta )\) since \(x_0=0\). By the estimates discussed in Sect. 1.5,
Next, we assume that \(i\ge 1\). Then \(x_{i+1}\le O(x_i)\) and, for all \(\ell \ge r\),
For the lower bound, first note that
and so
Hence, using (1) and (19) (and the standard bounds \((n-k)^k\le {n\atopwithdelims ()k}k!\le n^k\) and \((1-x)^y\ge 1-xy\)) we find
The upper bound requires slightly more attention. Note that, by the choice of m, \(\log m\ll x_1\vartheta \). Therefore \(\log m\le x_i\vartheta \) for all large n. Hence, for all large n,
Since \(p\vartheta \ll 1\ll m\), for all large n,
Therefore, by (1), (19) and the choice of m,
Next, by (19), it follows that, for all \(\ell \le \log m\) and large n,
Therefore, by (1) and (19), for all large n,
Altogether, we find that
as claimed. \(\square \)
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Angel, O., Kolesnik, B. Large Deviations for Subcritical Bootstrap Percolation on the Erdős–Rényi Graph. J Stat Phys 185, 8 (2021). https://doi.org/10.1007/s10955-021-02819-w
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10955-021-02819-w