2025-11-18T11:25:12.590731

Thresholds for contagious sets in random graphs

Angel, Kolesnik
For fixed $r\geq 2$, we consider bootstrap percolation with threshold $r$ on the Erdős-Rényi graph ${\cal G}_{n,p}$. We identify a threshold for $p$ above which there is with high probability a set of size $r$ which can infect the entire graph. This improves a result of Feige, Krivelevich and Reichman, which gives bounds for this threshold, up to multiplicative constants. As an application of our results, we also obtain an upper bound for the threshold for $K_4$-bootstrap percolation on ${\cal G}_{n,p}$, as studied by Balogh, Bollobás and Morris. We conjecture that our bound is asymptotically sharp. These thresholds are closely related to the survival probabilities of certain time-varying branching processes, and we derive asymptotic formulae for these survival probabilities which are of interest in their own right.
academic

Thresholds for contagious sets in random graphs

Basic Information

  • Paper ID: 1611.10167
  • Title: Thresholds for contagious sets in random graphs
  • Authors: Omer Angel, Brett Kolesnik
  • Classification: math.PR (Probability Theory), math.CO (Combinatorics)
  • Submission Date: November 30, 2016 (arXiv)
  • Paper Link: https://arxiv.org/abs/1611.10167

Abstract

This paper investigates the bootstrap percolation process with threshold rr on Erdős-Rényi random graphs Gn,pG_{n,p}. For fixed r≥2r \geq 2, the authors precisely identify the threshold for edge probability pp beyond which there exists, with high probability, a set of size rr capable of infecting the entire graph. This result improves upon the work of Feige, Krivelevich, and Reichman, elevating the threshold from multiplicative constant bounds to asymptotically exact results. As an application, the authors also obtain upper bounds for the K4K_4-bootstrap percolation threshold and conjecture that this bound is asymptotically optimal. These thresholds are closely related to the survival probabilities of certain time-varying branching processes, for which the authors derive asymptotic formulas.

Research Background and Motivation

Research Problem

Bootstrap percolation is a dynamic propagation process: given a graph G=(V,E)G=(V,E) and initial infected set V0⊂VV_0 \subset V, at each time step, any vertex with at least rr infected neighbors becomes infected and remains infected. The core questions are:

  1. Susceptibility Threshold Problem: In random graph Gn,pG_{n,p}, how large must edge probability pp be to guarantee with high probability the existence of a set of size rr (minimal contagious set) capable of infecting the entire graph?
  2. Graph Bootstrap Percolation: What is the threshold for K4K_4-bootstrap percolation (an edge-addition rule)?

Problem Importance

  • Theoretical Significance: Bootstrap percolation is an important model in statistical physics, computer science, neural networks, and sociology, used to study disordered magnetic systems, information propagation, opinion dynamics, and related phenomena
  • Mathematical Challenge: Bootstrap percolation on random graphs involves complex dependency structures, and determining precise thresholds requires sophisticated combinatorial and probabilistic techniques
  • Phase Transition Phenomena: The problem exhibits clear phase transition behavior—near the critical threshold, the system transitions sharply from "almost impossible global infection" to "high probability global infection"

Limitations of Existing Methods

Feige, Krivelevich, and Reichman 24 provided upper and lower bounds for the susceptibility threshold, but only up to multiplicative constants. Specifically, they could not determine the precise constant factor αr\alpha_r. The main contribution of this paper is to identify this exact constant.

Research Motivation

The authors discover that the susceptibility threshold is closely related to the survival probability of a class of non-homogeneous branching processes. By establishing this connection and precisely analyzing the branching process, one can obtain exact asymptotic expressions for the threshold.

Core Contributions

  1. Precise Threshold Identification (Theorem 1.1): For rr-bootstrap percolation, proves that the critical edge probability is pc(n,r)=(αrnlog⁡r−1n)1/r(1+o(1))p_c(n,r) = \left(\frac{\alpha_r}{n\log^{r-1}n}\right)^{1/r}(1+o(1)) where αr=(r−1)!(r−1r)2(r−1)\alpha_r = (r-1)!\left(\frac{r-1}{r}\right)^{2(r-1)}
  2. K4K_4-Bootstrap Percolation Upper Bound (Theorem 1.2): Proves that pc(n,K4)≤1+o(1)3nlog⁡np_c(n,K_4) \leq \frac{1+o(1)}{\sqrt{3n\log n}} and conjectures that this bound is asymptotically optimal
  3. Seed Edge Threshold (Theorem 1.4): For p=α/(nlog⁡n)p=\sqrt{\alpha/(n\log n)}, proves that Gn,pG_{n,p} contains a seed edge with high probability when α>1/3\alpha > 1/3
  4. Branching Process Survival Probability (Theorem 1.5): For the related non-homogeneous branching process, derives the asymptotic formula for survival probability P(Xt>0,∀t)=exp⁡[−(r−1)2rkr(1+o(1))]P(X_t > 0, \forall t) = \exp\left[-\frac{(r-1)^2}{r}k_r(1+o(1))\right] where kr=((r−1)!ε)1/(r−1)k_r = \left(\frac{(r-1)!}{\varepsilon}\right)^{1/(r-1)}
  5. Methodological Innovation: Introduces the concept of "triangle-free susceptible graphs" and restricts analysis to these special graphs to establish approximate independence of contagious sets, making the second moment method feasible

Detailed Methodology

Task Definition

rr-Bootstrap Percolation:

  • Input: Graph G=(V,E)G=(V,E), initial infected set V0⊂VV_0 \subset V, threshold rr
  • Evolution Rule: Vt+1=Vt∪{v:∣N(v)∩Vt∣≥r}V_{t+1} = V_t \cup \{v : |N(v) \cap V_t| \geq r\}
  • Output: Final infected set V∞=⟨V0,G⟩rV_\infty = \langle V_0, G \rangle_r

Contagious Set: If ⟨I,G⟩r=V\langle I, G \rangle_r = V, then II is called a contagious set of GG

Susceptibility: Graph GG is called susceptible or rr-percolating if it contains a contagious set of size rr (minimal contagious set)

Critical Probability: pc(n,r)=inf⁡{p>0:P(Gn,p is susceptible)≥1/2}p_c(n,r) = \inf\{p > 0 : P(G_{n,p}\text{ is susceptible}) \geq 1/2\}

Overall Architecture

The proof is divided into two main parts:

1. Lower Bound Proof (Section 2): Proves non-susceptibility when α<αr\alpha < \alpha_r

Core Idea: Uses the first moment method to prove that when pp is small, any set of size rr can only infect O(log⁡n)O(\log n) vertices.

Key Steps:

  • Establishes recurrence relations to compute the number of minimal susceptible graphs mr(k,i)m_r(k,i) (size kk, with ii vertices in the top layer)
  • Derives upper bounds for the normalized quantity σr(k,i)\sigma_r(k,i) (Lemma 2.5)
  • Defines critical parameter β∗(α)\beta^*(\alpha) as the unique positive root of: r+βlog⁡(αβr−1(r−1)!)−αβrr!−β(r−2)=0r + \beta\log\left(\frac{\alpha\beta^{r-1}}{(r-1)!}\right) - \frac{\alpha\beta^r}{r!} - \beta(r-2) = 0
  • Proves that when α<αr\alpha < \alpha_r, any rr-percolation grows to at most (β∗(α)+δ)log⁡n(\beta^*(\alpha)+\delta)\log n vertices (Proposition 2.1)

2. Upper Bound Proof (Section 3): Proves susceptibility when α>αr\alpha > \alpha_r

Core Idea: Uses the second moment method to prove existence of contagious sets. The main challenge is the dependency between contagious sets.

Innovative Strategy:

  • Introduces r^\hat{r}-percolation: Restricts to triangle-free susceptible subgraphs and defines r^\hat{r}-percolation process
  • Approximate Independence (Lemma 3.12): Uses Mantel's theorem (triangle-free graphs have at most v2/4v^2/4 edges) to prove approximate independence between different r^\hat{r}-percolations
  • Lower Bound Estimates: Proves that the number of triangle-free susceptible graphs is asymptotically the same as general susceptible graphs (Lemma 3.5)
  • Supercritical Growth: Proves that percolations exceeding critical size βr(α)log⁡n\beta_r(\alpha)\log n continue growing to linear scale

Technical Details

Recurrence Relations (Equation 2.1)

For the number of minimal susceptible graphs: mr(k,i)=(k−ri)∑j=1k−r−iar(k−i,j)imr(k−i,j)m_r(k,i) = \binom{k-r}{i}\sum_{j=1}^{k-r-i} a_r(k-i,j)^i m_r(k-i,j) where ar(x,y)=(xr)−(x−yr)a_r(x,y) = \binom{x}{r} - \binom{x-y}{r} represents the number of connection options for top-layer vertices.

Normalization Transform (Equation 2.3)

Define σr(k,i)=mr(k,i)(k−r)!((r−1)!kr−1)k\sigma_r(k,i) = \frac{m_r(k,i)}{(k-r)!}\left(\frac{(r-1)!}{k^{r-1}}\right)^k which transforms the recurrence into a form amenable to spectral analysis.

Triangle-Free Graph Recurrence (Equation 3.1)

m^r(k,i)≥(k−ri)∑j=1k−r−ia^r(k−i,j)im^r(k−i,j)\hat{m}_r(k,i) \geq \binom{k-r}{i}\sum_{j=1}^{k-r-i} \hat{a}_r(k-i,j)^i \hat{m}_r(k-i,j) where a^r(x,y)=max⁡{0,ar(x,y)−2ryxr−2}\hat{a}_r(x,y) = \max\{0, a_r(x,y) - 2ryx^{r-2}\} subtracts connection methods that might create triangles.

Approximate Independence (Lemma 3.12)

For disjoint sets I≠I′I \neq I' of size rr with ∣I∩I′∣=m|I \cap I'| = m:

(1+o(1))\hat{P}_r(k) & m=0\\ o((n/k)^m)\hat{P}_r(k) & 1 \leq m < r \end{cases}$$ The key is applying Mantel's theorem (Lemma 3.14): triangle-free graphs have at most $\lfloor v^2/4 \rfloor$ edges. ### Technical Innovations 1. **Branching Process Connection**: First establishes precise connection between susceptibility threshold and survival probability of non-homogeneous branching processes. In the branching process, the $n$-th individual has $\text{Poi}(\binom{n}{r-1}\varepsilon)$ offspring, where $\varepsilon = np^r$ 2. **Triangle-Free Restriction**: By restricting to triangle-free susceptible graphs, cleverly transforms the dependency problem into a tractable form. This works because the sparsity of triangle-free graphs (Mantel's theorem) ensures "separation" between different percolations 3. **Two-Phase Analysis**: - **Subcritical Phase** ($k < \beta_r(\alpha)\log n$): Percolations may survive but grow slowly - **Supercritical Phase** ($k > \beta^*(\alpha)\log n$): Percolations continue growing to linear scale with high probability 4. **Fine Combinatorial Estimates**: For susceptible graphs with different top-layer sizes $i$, requires fine lower bound estimates (Lemma 3.6), crucial for analyzing supercritical percolation 5. **Multi-Scale Coupling**: By adding independent random graphs $G_0, G_1, \ldots$ (with decreasing edge probabilities), proves that large susceptible subgraphs can infect the entire graph (final part of Theorem 1.1 proof) ## Experimental Setup **Note**: This is a pure theoretical mathematics paper with no numerical experiments or datasets. All results are obtained through rigorous mathematical proofs. The "experiments" are theoretical analyses and asymptotic estimates. ### Theoretical Verification Methods 1. **Asymptotic Analysis**: All results hold in the asymptotic sense as $n \to \infty$ 2. **Probability Estimates**: Uses "with high probability" (w.h.p.) to denote probability approaching 1 as $n \to \infty$ 3. **Exact Constants**: Determines exact constant factors $\alpha_r$ through analytical computation ### Parameter Settings - **Threshold Parameter**: $r \geq 2$ (fixed) - **Edge Probability**: $p = \left(\frac{\alpha}{n\log^{r-1}n}\right)^{1/r}$ - **Critical Constant**: $\alpha_r = (r-1)!\left(\frac{r-1}{r}\right)^{2(r-1)}$ - **Branching Process Parameters**: $\varepsilon = np^r = \alpha/\log^{r-1}n$, $k_r = \left(\frac{(r-1)!}{\varepsilon}\right)^{1/(r-1)}$ ## Experimental Results ### Main Theoretical Results #### 1. Precise Threshold (Theorem 1.1) **Result Statement**: For $p = \left(\frac{\alpha}{n\log^{r-1}n}\right)^{1/r}$: - **Supercritical** ($\alpha > \alpha_r$): $G_{n,p}$ is susceptible with high probability - **Subcritical** ($\alpha < \alpha_r$): Any set of size $r$ in $G_{n,p}$ infects at most $\beta\log n$ vertices (for some $\beta = \beta(\alpha,r)$) **Exact Asymptotics**: $$p_c(n,r) = \left(\frac{\alpha_r}{n\log^{r-1}n}\right)^{1/r}(1+o(1))$$ **Concrete Examples**: - $r=2$: $\alpha_2 = 1/4$, so $p_c(n,2) \sim \frac{1}{2}\sqrt{\frac{1}{n\log n}}$ - $r=3$: $\alpha_3 = 2 \cdot (2/3)^4 = 16/81$, so $p_c(n,3) \sim \left(\frac{16}{81n\log^2 n}\right)^{1/3}$ #### 2. $K_4$-Bootstrap Percolation (Theorem 1.2) **Result**: $$p_c(n,K_4) \leq \frac{1+o(1)}{\sqrt{3n\log n}}$$ **Conjecture**: This upper bound is asymptotically optimal, i.e., $$p_c(n,K_4) = \frac{1+o(1)}{\sqrt{3n\log n}}$$ This improves upon Balogh, Bollobás, and Morris [13] result $p_c(n,K_4) = \Theta(1/\sqrt{n\log n})$, providing the exact constant factor $1/\sqrt{3}$. #### 3. Seed Edge Threshold (Theorem 1.4) For $p = \sqrt{\alpha/(n\log n)}$: - $\alpha > 1/3$: $G_{n,p}$ contains a seed edge with high probability - $\alpha < 1/3$: $G_{n,p}$ does not contain a seed edge with high probability **Seed Edge Definition**: Edge $(x_0,x_1)$ is a seed edge if there exists a vertex ordering such that $x_0,x_1$ form a clique and each subsequent vertex connects to at least 2 previous vertices. #### 4. Branching Process Survival Probability (Theorem 1.5) $$P(X_t > 0, \forall t) = \exp\left[-\frac{(r-1)^2}{r}k_r(1+o(1))\right]$$ where $k_r = \left(\frac{(r-1)!}{\varepsilon}\right)^{1/(r-1)}$ is approximately the time when the process becomes supercritical. ### Key Lemma Results #### Lemma 2.5 (Upper Bound for Susceptible Graph Count) $$m_r(k,i) \leq \frac{e^{-i-(r-2)k}}{\sqrt{i}}(k-r)!\left(\frac{k^{r-1}}{(r-1)!}\right)^k$$ Equivalently, $\sigma_r(k,i) \leq i^{-1/2}e^{-i-(r-2)k}$ #### Lemma 3.5 (Lower Bound for Triangle-Free Susceptible Graph Count) $$m_r(k) \geq \hat{m}_r(k) \geq e^{-o(k)}e^{-(r-2)k}(k-r)!\left(\frac{k^{r-1}}{(r-1)!}\right)^k$$ This shows that restricting to triangle-free graphs loses only an $e^{-o(k)}$ factor, not affecting the main asymptotic behavior. #### Lemma 3.6 (Lower Bound for Susceptible Graphs with Large Top Layer) For $\varepsilon \in (0, 1/(r+1))$ and $i \leq (\varepsilon/r)^2k$: $$\hat{m}_r(k,i) \geq e^{-i\varepsilon-(r-2)k-o(k)}(k-r)!\left(\frac{(k-i)k^{r-2}}{(r-1)!}\right)^k$$ This is crucial for analyzing the growth of supercritical percolations. ### Analysis and Insights 1. **Clarity of Phase Transition**: Behavior on both sides of threshold $\alpha_r$ is completely different—subcritical shows only logarithmic growth, supercritical shows global infection 2. **Role of Branching Process**: The critical constant $\alpha_r$ exactly corresponds to the transition point of the related branching process from subcritical to supercritical 3. **Significance of $\beta^*(\alpha)$**: - When $\alpha < \alpha_r$: $\beta^*(\alpha) > \beta_r(\alpha)$, percolation stops before reaching "would-be" supercritical size - When $\alpha = \alpha_r$: $\beta^*(\alpha_r) = \beta_r(\alpha_r)$, exactly at critical point - When $\alpha > \alpha_r$: $\beta^*(\alpha) < \beta_r(\alpha)$, percolation can exceed critical size and continue growing 4. **Special Role of Seed Edges**: For $r=2$ ($K_4$-bootstrap), seed edges are the easiest infection method. But for $r>2$, seeds are no longer optimal, as $K_{r+2}$-bootstrap threshold is much lower than seed threshold ## Related Work ### History of Bootstrap Percolation 1. **Origins**: Chalupa, Leath, and Reich [20] introduced bootstrap percolation in 1979 to study disordered magnetic systems 2. **Research on Lattices and Grids**: - Aizenman and Lebowitz [3]: Metastability effects - Cerf and Cirillo [18], Cerf and Manzo [19]: Three-dimensional finite-size scaling - Holroyd [33], Gravner, Holroyd, and Morris [32]: Two-dimensional exact thresholds - Balogh, Bollobás, and Morris [9, 10, 12]: Exact thresholds in all dimensions 3. **Research on Random Graphs**: - Janson et al. [36]: Critical size of random initial sets - Balogh and Pittel [16]: Random regular graphs - Amini [4], Amini and Fountoulakis [5]: Random graphs with given degree sequences 4. **Minimal Contagious Sets**: - Feige, Krivelevich, and Reichman [24]: First study of minimal contagious set thresholds on $G_{n,p}$, providing $\Theta$ bounds - **This Paper**: Improves to exact asymptotic results ### Graph Bootstrap Percolation 1. **Definition**: Introduced by Bollobás [17], rule is to add missing edges of $H$ copies 2. **$K_k$-Bootstrap Percolation**: - Balogh, Bollobás, and Morris [13]: Prove $p_c(n,K_4) = \Theta(1/\sqrt{n\log n})$ - **This Paper**: Improves upper bound to $(1+o(1))/\sqrt{3n\log n}$, determining exact constant factor $1/\sqrt{3}$ 3. **Role of Seeds**: - Lemma 1.3: If there is a seed for $K_{r+2}$-bootstrap, the graph fully percolates - For $K_4$, seed edges are the simplest percolation method (conjectured) - For $K_k$ ($k>4$), seeds are not the simplest method ### Branching Processes Non-homogeneous branching processes have applications in many fields. The specific model introduced in this paper (where the $n$-th individual has $\text{Poi}(\binom{n}{r-1}\varepsilon)$ offspring) is new, and its exact asymptotic formula for survival probability (Theorem 1.5) has independent theoretical interest. ## Conclusions and Discussion ### Main Conclusions 1. **Precise Threshold Identification**: First provides exact asymptotic expression for $r$-bootstrap percolation susceptibility threshold, determining constant factor $\alpha_r = (r-1)!(r-1)^{2(r-1)}/r^{2(r-1)}$ 2. **Methodological Contributions**: - Establishes precise connection between susceptibility threshold and non-homogeneous branching processes - Introduces triangle-free restriction to handle dependency problems - Develops fine combinatorial counting techniques 3. **Applications**: Improves $K_4$-bootstrap percolation threshold upper bound, conjectures it is optimal ### Limitations 1. **$K_4$-Bootstrap Lower Bound**: Paper only provides upper bound $1/\sqrt{3n\log n}$, conjectures it is exact threshold but does not prove lower bound. For $r>2$, seeds are no longer the simplest percolation method, requiring new approaches 2. **Complexity of Constants**: While providing exact $\alpha_r$, its expression is complex and not intuitive 3. **Non-Asymptotic Behavior**: All results are asymptotic ($n \to \infty$), no exact estimates for finite $n$ 4. **Generalizability**: Methods heavily depend on specific structure of Erdős-Rényi random graphs. Extending to other random graph models (configuration model, geometric random graphs) may require new techniques ### Future Directions 1. **$K_4$-Bootstrap Lower Bound**: Prove or disprove conjecture $p_c(n,K_4) \sim 1/\sqrt{3n\log n}$ 2. **More General $K_k$-Bootstrap**: For $k>4$, determine exact thresholds. Paper notes this is harder than seed threshold analysis 3. **Other Graph Classes**: Extend methods to other $H$-bootstrap percolation 4. **Algorithmic Problems**: Given $G_{n,p}$, how to efficiently find minimal contagious set (if it exists)? 5. **Dynamic Processes**: Study time evolution of bootstrap percolation, not just final state 6. **Fine Structure of Subcritical Behavior**: Proposition 2.1 shows subcritical percolation grows to $\beta^*(\alpha)\log n$. Can we precisely characterize behavior near $\beta^*(\alpha)$? ## In-Depth Evaluation ### Strengths #### 1. Theoretical Depth - **Exact Results**: Elevation from multiplicative constant bounds to exact asymptotic expressions represents major progress in random graph theory - **Novel Connections**: First establishes precise connection between susceptibility threshold and branching process survival probability. This cross-domain connection has deep theoretical significance - **Completeness**: Proves both upper and lower bounds, providing complete phase transition picture #### 2. Technical Innovation - **Triangle-Free Restriction**: Clever approach to handling dependency problems. Via Mantel's theorem, sparsity of triangle-free graphs naturally provides "independence" - **Multi-Scale Analysis**: Distinguishes subcritical, critical, and supercritical phases, using different techniques for each - **Fine Combinatorial Estimates**: Lemma 3.6 for lower bounds on susceptible graphs with large top layers is technically challenging, requiring careful induction and asymptotic analysis #### 3. Proof Rigor - **Complete Proofs**: All main results have detailed proofs, with technical lemmas in appendices - **Fine Asymptotic Analysis**: Careful treatment of $o(1)$ terms, clearly indicating which depend on $n$ and which on other parameters - **Boundary Case Handling**: Careful treatment of various boundary cases (e.g., $i=k-r$, $k$ near critical size) #### 4. Writing Quality - **Clear Structure**: Well-organized paper, flowing logically from problem definition to main results to detailed proofs - **Intuitive Explanations**: Usually provides intuitive explanations before technical proofs (e.g., Section 1.4 proof outline) - **Consistent Notation**: Though notation is extensive, definitions are clear and usage consistent ### Weaknesses #### 1. Technical Complexity - **Proof Length**: Main proofs are very long (Section 3 ~20 pages), involving extensive technical details, high difficulty to understand - **Nested Recurrences**: Recurrence relations (e.g., Equations 2.1, 3.1) have multiple nesting levels, difficult to track - **Constant Calculation**: Expression for $\alpha_r$, while exact, is not intuitive, lacks simple numerical table or approximation formula #### 2. Result Completeness - **Missing $K_4$-Bootstrap Lower Bound**: Only upper bound provided, conjecture unproven - **No Non-Asymptotic Bounds**: No explicit bounds for finite $n$, unclear when asymptotic results become valid - **Implicit $\beta^*(\alpha)$**: Defined by implicit equation, lacks explicit expression #### 3. Generalizability Limitations - **Model-Specific**: Methods highly dependent on $G_{n,p}$ independence and symmetry - **Fixed Threshold Parameter**: Only considers fixed $r$, unclear what happens when $r$ grows (e.g., $r=r(n)$) - **General Graph Classes**: Unclear if methods apply to non-$K_k$ $H$-bootstrap percolation #### 4. Practical Utility - **Pure Theory**: No numerical verification or simulation, cannot assess accuracy of asymptotic results at practical scales (e.g., $n=10^6$) - **No Algorithms**: No discussion of actually finding contagious sets or verifying susceptibility - **Limited Applications**: While mentioning application domains, provides no concrete application cases ### Impact #### Contributions to Field 1. **Random Graph Theory**: Provides new analytical tools for dynamic processes on random graphs (triangle-free restriction technique) 2. **Percolation Theory**: Deepens understanding of bootstrap percolation phase transitions, particularly exact critical constants 3. **Branching Processes**: Introduces new non-homogeneous branching process model with exact survival probability formula 4. **Combinatorics**: Develops recurrence techniques for counting susceptible graphs #### Practical Value - **Theoretical Benchmark**: Provides theoretical baseline for information propagation, disease spread on actual networks - **Algorithm Design**: While paper doesn't discuss algorithms, exact threshold values can guide contagious set search algorithm design - **Parameter Selection**: In network design, can select connection density based on thresholds to avoid or promote global propagation #### Reproducibility - **Theoretical Results**: Complete proofs, in principle verifiable - **Numerical Verification**: Though no numerical experiments, Theorem 1.5 (branching process survival probability) can be verified via Monte Carlo simulation - **Code Missing**: No code or numerical experiments provided, limiting practical application ### Applicable Scenarios #### Theoretical Research 1. **Random Graph Theory**: Study thresholds for other dynamic processes on $G_{n,p}$ 2. **Percolation Theory**: Generalize to other bootstrap percolation types or graph classes 3. **Extremal Combinatorics**: Susceptible graph counting has independent combinatorial interest #### Practical Applications 1. **Social Networks**: Understand information/behavior propagation conditions in sparse social networks 2. **Epidemiology**: Model disease spread requiring multiple contacts for infection 3. **Network Reliability**: Analyze cascade failure conditions (reverse perspective: avoid global infection) 4. **Neural Networks**: Understand neuron activation threshold effects #### Limitations - **Density Range**: Only applies to $p = \Theta(n^{-1/r}\log^{-(r-1)/r}n)$ sparse graphs - **Homogeneity**: Assumes all vertices and edges homogeneous, actual networks typically heterogeneous - **Static Structure**: Ignores dynamic network structure changes ## Key References 1. **[20] Chalupa, Leath, Reich (1979)**: Original bootstrap percolation paper 2. **[24] Feige, Krivelevich, Reichman (2016)**: Prior work improved by this paper, providing $\Theta$ bounds 3. **[13] Balogh, Bollobás, Morris (2012)**: Graph bootstrap percolation, application target of this paper 4. **[36] Janson et al. (2012)**: Bootstrap percolation on $G_{n,p}$ with random initial sets 5. **[23] Erdős, Rényi (1959)**: Foundational work in random graph theory 6. **[39] Mantel (1907)**: Mantel's theorem, key tool in this paper's proofs 7. **[44] Turán (1941)**: Turán's theorem, generalization of Mantel's theorem --- ## Summary This is a high-quality theoretical mathematics paper making important contributions to bootstrap percolation on random graphs. The main achievement is elevating the susceptibility threshold from multiplicative constant bounds to exact asymptotic expressions, determining constant factor $\alpha_r$. Technical innovations (particularly triangle-free restriction and branching process connection) not only solve this paper's problems but also provide new tools for related fields. The paper's main limitations are high technical complexity, incomplete results (e.g., $K_4$-bootstrap lower bound), and lack of numerical verification. However, given problem difficulty and result precision, these shortcomings are acceptable. For researchers in random graph theory and percolation theory, this is essential reading. For applied researchers, the threshold formulas provide theoretical benchmarks for actual network analysis, but must note model assumptions (sparsity, homogeneity) applicability.