Sharp Fuss-Catalan Thresholds in Graph Bootstrap Percolation

Basic Information

• Paper ID: 2510.26724
• Title: Sharp Fuss-Catalan thresholds in graph bootstrap percolation
• Authors: Zsolt Bartha, Brett Kolesnik, Gal Kronenberg, Yuval Peled
• Classification: math.PR (Probability Theory), math.CO (Combinatorics)
• Submission Date: October 30, 2025 to arXiv
• Paper Link: https://arxiv.org/abs/2510.26724

Abstract

This paper investigates graph bootstrap percolation on Erdős-Rényi random graphs $G_{n,p}$. For all $r \geq 5$, the authors precisely locate the sharp threshold $p_c \sim (\gamma n)^{-1/\lambda}$ for $K_r$-percolation, resolving an open problem posed by Balogh, Bollobás, and Morris. For $r=3$, this corresponds to the classical graph connectivity threshold; for $r=4$, the threshold has been resolved through connections with 2-neighbor dynamics in statistical physics. However, for $r \geq 5$, this connection breaks down, and the process exhibits richer behavior. The constants $\lambda=\lambda(r)$ and $\gamma=\gamma(r)$ in the threshold $p_c$ are determined by a class of $\binom{r}{2}-1$-ary tree-like graphs, which the authors call $K_r$-tree witness graphs. These graphs correspond to the most efficient ways of adding new edges in $K_r$-dynamics and can be counted using Fuss-Catalan numbers. Furthermore, in the subcritical regime, the authors determine the asymptotic behavior of the number of edges added to $G_{n,p}$, proving that edge density increases by only an identifiable constant factor.

Research Background and Motivation

Problem Background

1. Core Problem of Graph Bootstrap Percolation: Given a template graph $H$ and an initial graph $G \subseteq K_n$, the $H$-bootstrap percolation process adds a new edge $e$ at each step if there exists a copy of $H$ in $K_n$ where $e$ is the unique edge not yet added to $G$. If $G$ eventually evolves to the complete graph $K_n$, then $G$ is called weakly $H$-saturated or $H$-percolating.
2. Importance of Threshold Probability: For the Erdős-Rényi random graph $G_{n,p}$, the critical threshold $p_c(n,H)$ is defined as the minimum $p$ value such that $P(\langle G_{n,p}\rangle_H = K_n) \geq 1/2$. This is a central problem in random graph theory, generalizing the classical graph connectivity threshold.
3. Limitations of Known Results:
   • $r=3$: Classical result $p_c(n,K_3) \sim \log n/n$ (graph connectivity)
   • $r=4$: $p_c(n,K_4) \sim (3n\log n)^{-1/2}$, obtained through connection with 2-neighbor dynamics
   • $r \geq 5$: Balogh et al. 8 only determined $p_c(n,K_r) = n^{-1/\lambda + o(1)}$, where $\lambda = \frac{\binom{r}{2}-2}{r-2}$, precise up to polylogarithmic factors

Research Motivation

1. Resolving Open Problems: Balogh et al. posed three problems in 8, and this paper resolves two of them in strong form:
   • Problem 2: Determine which $H$ have sharp thresholds
   • Problem 3: Determine $p_c(n,K_r)$ up to constant factors
2. Phase Transition at $r \geq 5$: When $r \geq 5$, $K_r$ becomes strictly balanced, the connection with $(r-2)$-neighbor dynamics breaks, and the process no longer propagates through "nucleation" but exhibits entirely new behavior patterns.
3. Theoretical Challenge: New combinatorial techniques are needed to analyze the structure of witness graphs, particularly to control the propagation of "zero-cost" edges, which is the core technical innovation of this paper.

Core Contributions

1. Sharp Threshold Theorem (Theorem 1.1): For all $r \geq 5$, it is proved that $p_c(n,K_r) \sim (\gamma n)^{-1/\lambda}$ where $\gamma$ is uniquely determined by the asymptotic growth rate of Fuss-Catalan numbers $\alpha_{\binom{r}{2}-2}$: $(r-2)!\gamma^{r-2} = \alpha_{\binom{r}{2}-2} = \frac{(\binom{r}{2}-1)^{\binom{r}{2}-1}}{(\binom{r}{2}-2)^{\binom{r}{2}-2}}$
2. Subcritical Edge Expansion Theorem (Theorem 1.2): In the subcritical region $p = (\bar{\gamma}n)^{-1/\lambda}$ ($\bar{\gamma} > \gamma$), it is proved that $|E(\langle G_{n,p}\rangle_{K_r})| \sim \rho \cdot p\binom{n}{2}$ where $\rho > 1$ is the smallest root of the equation $\rho^{\binom{r}{2}-1} = \bar{\alpha}(\rho-1)$.
3. Tree Decomposition Method: Introduces a tree decomposition technique for witness graphs, decomposing any witness graph into a "bad part" and multiple "tree parts," proving that the number of tree parts is $O(\kappa)$, where $\kappa$ is the total cost.
4. $(r-2)^*$-Bootstrap Percolation Process: Innovatively introduces a modified $(r-2)$-neighbor dynamics to control the propagation of zero-cost edges within tree parts, which is the key tool for proving the sharp lower bound.
5. Refined Combinatorial Counting: Refines the counting of witness graphs from $A^\sigma\sigma!$ ($A > \gamma$) to $\gamma^\sigma\sigma!\sigma^{O(\kappa^2)}$, which is crucial for obtaining the sharp constant.

Detailed Methodology

Task Definition

Input: Erdős-Rényi random graph $G_{n,p}$, template graph $H = K_r$ ($r$-clique)
Output: Critical threshold $p_c(n,K_r)$ such that $P(\langle G_{n,p}\rangle_{K_r} = K_n)$ transitions from near 0 to near 1
Constraint: Precision up to constant factors, i.e., determining the constant $\gamma$ in $p_c \sim (\gamma n)^{-1/\lambda}$

Core Conceptual Framework

1. Witness Graphs

For each edge $e$ added in $K_r$-dynamics, there exists a witness graph $W(e) \subseteq G$ such that $e \in E(\langle W(e)\rangle_{K_r})$. Witness graphs are recursively defined via the Witness Graph Algorithm (WGA):

• If $e \in E_0$ (initial edges), then $W(e) = e$
• Otherwise, select a copy $H(e)$ of $K_r$ such that $E(H(e)\setminus e) \subset \bigcup_{s<t}E_s$, and set $W(e) = \bigcup_{f \in E(H(e)\setminus e)}W(f)$

2. $K_r$-Tree Witness Graphs (TWG)

TWGs are witness graphs with the minimum number of edges, recursively defined as:

• Base case: A single edge $e$ is a 0-TWG
• Recursive construction: A $k$-TWG is obtained by:
  • Taking a $(k-1)$-TWG $T'$
  • Removing one edge $e'$ from it
  • Replacing it with a copy of $K_r$ containing $e'$ (minus $e'$)

Key Properties (Lemma 3.6):

• Number of vertices: $v(T) = (r-2)k + 2$
• Number of edges: $e(T) = \lambda(r-2)k + 1$, where $\lambda = \frac{\binom{r}{2}-2}{r-2}$
• Tree-like structure: Can be represented as a $\binom{r}{2}-1$-ary tree

3. Connection to Fuss-Catalan Numbers

The number of $k$-TWGs is (Lemma 3.8): $t(k) = \frac{((r-2)k)!}{(r-2)!^k} \text{FC}_{\binom{r}{2}-2}(k)$ where the Fuss-Catalan number $\text{FC}_d(k) = \frac{1}{dk+1}\binom{(d+1)k}{k}$ has asymptotic growth rate $\alpha_d = \frac{(d+1)^{d+1}}{d^d}$.

Upper Bound Proof Strategy (Section 3)

Key Idea

In the supercritical region $p = ((1+\epsilon)\gamma n)^{-1/\lambda}$, prove that with high probability all edges can be added through logarithmic-order TWGs.

Technical Steps

1. Expected Counting of Balanced TWGs (Lemma 3.12): For a fixed edge $e$, the number of balanced $k$-TWGs (where all main branches have equal order) $B_k^{(e)}$ satisfies: $\mathbb{E}(B_k^{(e)}) \sim \phi' \frac{(1+\epsilon)^{(r-2)k}}{k^{3((\binom{r}{2}-1)/2)}}p$ When $k = \beta\log n$ ($\beta$ sufficiently large), the expected value $\gg n^c$.

2. Structural Lemma for Partial TWGs (Lemma 3.16): For a proper subgraph $S$ of TWG $T$, define three key parameters:

• Edge efficiency: $\mathcal{E}(S) = \lambda\sigma(S) - e(S) \geq 0$
• Intra-tree defect: $\mathcal{D}(S,T) = |P| \leq c\mathcal{E}(S) + 2$
• Tree extensibility: $\mathcal{T}(S) \leq c\mathcal{E}(S)$

where $\sigma(S) = |V(S)\setminus e|$ is the number of vertices not at the endpoints of the target edge.

3. Application of Janson's Inequality: Compute the variance term $\Delta = \sum_{T_1 \sim T_2}P(T_1,T_2 \subset G_{n,p})$, with the key observation that:

• If $S = T_1 \cap T_2$ has $\mathcal{E}(S) > 0$, then the factor $p^{\mathcal{E}(S)}$ provides sufficient decay
• If $\mathcal{E}(S) = 0$, then $S$ is obtained by removing branches, and by balance $\sigma(S) \geq ck$

Conclusion: $\Delta/\mu^2 \ll (k/n)^c$, Janson's inequality gives $P(B_k^{(e)} = 0) \ll n^{-2}$, and union bound proves full percolation.

Lower Bound Proof Strategy (Sections 5-6)

First Phase: Rough Lower Bound (Section 5)

Prove $p_c = \Omega(n^{-1/\lambda})$.

1. Tree Decomposition Construction: For any witness graph $W$, at each step of the Red Edge Algorithm (REA), decompose component $C$ into:

• Bad part $B$ (possibly empty)
• Tree parts $T_1,\ldots,T_k$ (each is a $K_r$-tree)

satisfying properties:

• If $B = \emptyset$, then $k=1$ and $C$ is a tree component
• If $B \neq \emptyset$, each $T_i$ intersects $B$ at a single edge (called the base edge), and tree parts are pairwise edge-disjoint

2. Complexity Bound (Lemma 5.7): Define the tree count $\tau(C)$ as the number of tree parts "compromised" (added to the bad part) in REA, prove: $\tau(C) = O(\kappa(C))$ where $\kappa(C)$ is the cost (number of vertices involved in expensive steps).

3. Combinatorial Counting (Lemma 5.10): The number of witness graphs of size $\sigma$ and cost $\kappa$ is at most: $A^\sigma \cdot \sigma! \cdot \sigma^{O(\kappa)}$ where $A > \gamma$ is some constant.

4. Expectation Calculation: Combining Lemma 4.9 ($\chi(W) \geq \xi\kappa(W)$) and the above counting, for $p = (\epsilon/n)^{1/\lambda}$ ($\epsilon < 1/\gamma$), the expected number of witness graphs: $\sum_{\sigma,\kappa}\binom{n}{\sigma}A^\sigma\sigma!\sigma^{O(\kappa)}p^{\lambda\sigma+1+\xi\kappa} \leq (\log n)^{O(\log\log n)}p\sum_\sigma(\epsilon A)^\sigma \to 0$

Second Phase: Sharp Lower Bound (Section 6)

Prove $p_c \sim (\gamma n)^{-1/\lambda}$.

Core Challenge: Need to refine counting from $A^\sigma$ to $\gamma^\sigma$, with the gap coming from non-TWG tree components.

Key Innovation 1: $(r-2)^*$-Bootstrap Percolation (Definition 6.2): Define a modified $(r-2)$-neighbor process on $K_r$-trees $T$, allowing special steps:

• Regular steps: A vertex with $\geq r-2$ infected neighbors becomes infected
• Special steps: For an internal edge $e$, if two $K_r$ copies $H_i,H_j$ containing $e$ have $H_i$ with $r-4$ infected vertices and $H_j$ with 1 infected vertex (neither on $e$), then infect a vertex of $e$

Key Innovation 2: Comparison Lemma (Lemma 6.3): Let $T$ be a $K_r$-tree, $G$ a graph, $S = V(G)\cap V(T)$. Then: $\langle G \cup T\rangle_{K_r} \subset Q \cup T$ where $Q$ is a clique on $V(G) \cup \langle S;T\rangle^*$, and $\langle S;T\rangle^*$ is the final infected set of the $(r-2)^*$-BP process.

Key Innovation 3: Expansion Lemma (Lemma 6.5): The $(r-2)^*$-BP process expands at most linearly: $|\langle S;T\rangle^*| = O(|S|)$.

Proof Technique:

• Track the number of neighbors at infection time, define $k$-steps (exactly $k$ edges connecting to infected vertices)
• Establish inequality systems through exploration processes (progressively revealing $K_r$ copies)
• Exploit the strict balance property of $r \geq 5$ to ensure special steps are "compensated" by subsequent regular steps

Propagation Lemma (Lemma 6.7): If $|V(T)\cap V(G)| = x$, then $K_r$-dynamics on $G\cup T$ uses at most $O(x)$ edges in $T$.

Refined Combinatorial Counting (Lemma 6.10): Using Lemma 6.8 (each maximal tree part has at most $O(\kappa)$ target edges), prove: $\text{Number of witness graphs} \leq \gamma^\sigma \cdot \sigma! \cdot \sigma^{O(\kappa^2)}$

Final Argument: For $p = ((1-\epsilon)\gamma n)^{-1/\lambda}$, the expected number of witness graphs: $\sum_{\sigma,\kappa}\binom{n}{\sigma}\gamma^\sigma\sigma!\sigma^{O(\kappa^2)}p^{\lambda\sigma+1+\xi\kappa} \leq (\log n)^{O((\log\log n)^2)}p\sum_\sigma(1-\epsilon)^\sigma \to 0$

Technical Innovations

1. Innovative Tree Decomposition Design

• Dynamic Maintenance: Dynamically update decomposition at each REA step while maintaining three key properties
• Bad Tree Step Handling: Add auxiliary tree $T$ to bad part rather than as tree part, which is crucial for controlling tree part count
• Tight Connection to Cost: Prove $\omega(W) = O(\kappa(W))$ and $\sum|V(T_i)| = \sigma + O(\kappa)$

2. Clever Design of $(r-2)^*$-BP

• Priority Mechanism: Prioritize regular steps, use special steps only when necessary
• Correspondence with $K_r$-Dynamics: Special steps precisely capture the condition for edge propagation through "hinges"
• Linear Expansion Proof: Through refined counting arguments, exploit $r \geq 5$ to ensure special step costs are absorbed by subsequent steps

3. Deep Application of Strict Balance

Definition (Definition 3.17): Graph $H$ is strictly balanced if for all subgraphs $F$ with $3 \leq v(F) < v(H)$: $\frac{e(F)-1}{v(F)-2} < \lambda(H) = \frac{e(H)-2}{v(H)-2}$

Key Applications:

• Lemma 3.20: Control edge efficiency of leaves in partial TWGs
• Claim 5.3: Prove IntR steps don't propagate between tree parts
• Proof of Lemma 6.3: Ensure contradiction cases don't occur

4. Multi-Scale Analysis

• Logarithmic scale: TWG order $k = O(\log n)$
• Double logarithmic scale: Cost $\kappa = O(\log\log n)$
• Constant scale: Number of target edges in tree parts $O(\kappa)$

Experimental Setup

Simulation Study (Section 8.2)

Parameter Settings:

• Number of vertices: $n = 2000$
• Template graph: $K_5$ ($r=5$)
• Three phases: subcritical, near-critical, supercritical

Visualization Method:

• Matrix representation: Point $(i,j)$ represents edge $\{v_i,v_j\}$
• Color coding: Dark blue (initial edges) → yellow (last added), white (not added)
• Vertex ordering: Biased toward vertices with early-added edges

Observed Results:

1. Subcritical: Edge density increases by only constant factor, localized to 100 vertices
2. Supercritical: Slow growth in early stages, followed by "explosive" full percolation
3. Rounds: 4 rounds subcritical, 15 rounds supercritical

Limitations Discussion:

• $L = (np^{r-2})^{-1/(r-3)} \approx 1.6$ for $n=2000,r=5$ is too small
• Observed behavior dominated by 3-neighbor dynamics
• Need extremely large $n$ to observe true $r \geq 5$ behavior ("slow aging" phenomenon)

Experimental Results

Theoretical Result Verification

Specific Form of Theorem 1.1 ($r=5$): $p_c(n,K_5) \sim (\gamma n)^{-1/3}, \quad \gamma = \left(\frac{\alpha_8}{6}\right)^{1/3} = \left(\frac{9^9}{8^8 \cdot 6}\right)^{1/3} \approx 1.107$

Specific Form of Theorem 1.2 ($r=5$, $\bar{\gamma} = 1.2$):

• $\bar{\alpha} = 6 \times 1.2^3 \approx 10.368$
• $\rho$ satisfies $\rho^9 = 10.368(\rho-1)$, numerical solution $\rho \approx 1.52$
• Edge density increases by approximately 52%

Numerical Verification (Figure 1)

Subcritical Case (Figure 1a):

• Initial edge count: $\approx p\binom{n}{2} \approx 1000$
• Final edge count: $\approx 1.5 \times 1000 = 1500$
• Agrees with theoretical prediction $\rho \approx 1.52$

Supercritical Case (Figure 1c):

• All $\binom{2000}{2} \approx 2\times 10^6$ edges eventually added
• Two-stage behavior: Slow growth (dark blue to green) + explosive completion (orange to yellow)

Key Findings

1. Sharpness of Threshold: Percolation probability transitions from near 0 to near 1 between subcritical and supercritical, with window width $o(p_c)$
2. Dominance of TWGs:
   • Supercritical: Almost all edges added through logarithmic-order TWGs
   • Subcritical: $\rho$ factor completely determined by TWG contribution
3. Role of Cost:
   • Non-TWG witness graphs have cost $\kappa \geq 1$ providing additional factor $p^{\xi\kappa}$
   • This suffices to offset their increased count (from $\gamma^\sigma$ to $\gamma^\sigma\sigma^{O(\kappa^2)}$)
4. Phase Transition at $r \geq 5$:
   • No intermediate-scale percolating subgraph exists ($1 \ll k \ll L$)
   • Fundamentally different from $r=4$ nucleation mechanism

Related Work

Historical Context of Bootstrap Percolation

1. Classical Vertex Bootstrap Percolation:

• Chalupa et al. 18: Origin in statistical physics
• Aizenman-Lebowitz 1: Metastability properties on $\mathbb{Z}^d$
• Holroyd 30: Sharp metastability threshold in two dimensions
• Balogh et al. 7: Sharp thresholds in all dimensions
• Balister et al. 6: Universality conjecture for monotone cellular automata

2. $r$-Neighbor Dynamics on Random Graphs:

• Janson et al. 31: Detailed study on $G_{n,p}$
• Key distinction: Vertex infection vs. edge infection

3. Graph Bootstrap Percolation:

• Bollobás 15: Introduction of weak saturation, minimum edge count for $r \leq 6$
• Alon 2, Frankl 23, Kalai 32,33, Lovász 36: Generalizations to all $r$
• Balogh et al. 9: Hypergraph generalizations
• Balogh et al. 8: Thresholds on random graphs, direct predecessor of this work

Positioning of This Work

Progress Relative to 8:

• 8's result: $p_c(n,K_r) = n^{-1/\lambda+o(1)}$ (polylogarithmic precision)
• This work: $p_c(n,K_r) \sim (\gamma n)^{-1/\lambda}$ (constant precision)
• Resolves Problem 2 (sharpness) and Problem 3 (constant factors)

Technical Comparison:

• 8: Uses $K_r$-ladders + Aizenman-Lebowitz property
• This work: Tree decomposition + $(r-2)^*$-BP + Fuss-Catalan counting

Relation to Other Template Graphs $H$:

• Korándi-Sudakov 35 et al.: Saturation problems in $G_{n,p}$
• Bayraktar-Chakraborty 12, Bidgoli et al. 13: $K_{r,s}$-percolation
• Understanding for general $H$ remains widely open (Problem 1 in 8)

Cross-Disciplinary Connections

Hypergraph Bootstrap Percolation:

• Lubetzky-Peled 37: Fuss-Catalan-type thresholds in stacked triangulations
• Uses exterior algebra shifting, complementary to this work's combinatorial approach

Rigidity Theory:

• Kalai 32: Connection between weak saturation and $(r-2)$-rigidity
• This work attempted but failed to apply rigidity theory (Section 8.4)
• Open question: Can rigidity theory strengthen the propagation lemma?

Conclusions and Discussion

Main Conclusions

1. Complete Resolution of $r \geq 5$ Threshold Problem: $p_c(n,K_r) = \frac{1}{\gamma n^{1/\lambda}}(1+o(1))$ where $\gamma,\lambda$ are uniquely determined by asymptotic properties of Fuss-Catalan numbers.
2. Precise Characterization of Subcritical Edge Expansion: The edge density increase factor $\rho$ is determined by the generating function equation $\rho^{\binom{r}{2}-1} = \bar{\alpha}(\rho-1)$.
3. Revelation of New Mechanism for $r \geq 5$:
   • Propagation not through nucleation
   • TWGs dominate percolation process
   • Strict balance is essential

Limitations

1. Critical Window Not Determined:
   • Second-order terms unknown
   • Critical window width $\omega(n)$ undetermined
   • Fine structure of critical behavior unclear
2. "Critical Droplet" Not Identified:
   • Theory predicts scale $L = n^{(r-4)/(r^2-r-4)+o(1)}$
   • But proof doesn't directly construct such subgraphs
   • Relation to nucleation mechanism unclear
3. Simulation Limitations:
   • Need extremely large $n$ to observe true behavior (slow aging)
   • Current simulations mainly show $(r-2)$-neighbor dynamics
4. Method Applicability Range:
   • Heavily depends on $r \geq 5$ (strict balance)
   • Generalization to arbitrary $H$ requires new ideas
   • Rigidity theory approach unsuccessful

Future Directions

1. Fine Understanding of Critical Phenomena (Section 8.1):

• Determine critical window width
• Characterize "explosion" step in $G(n,m)$ evolution
• Identify critical droplets at scale $L$

2. Generalization to Strictly Balanced Graphs (Section 8.3):

• Conjecture: All strictly balanced $H$ satisfy $p_c = \Theta(n^{-1/\lambda})$
• Upper bound already proved by 10
• Lower bound requires generalizing tree decomposition and propagation lemma
• Key: Exploit additional factor $p^{\xi\kappa}$ ($\xi > 0$)

3. General Template Graphs $H$ (Problem 1 in 8):

• Determine $p_c(n,H)$ for all $H$
• Characterize sharpness conditions
• Behavior for balanced but non-strictly-balanced graphs

4. Application of Rigidity Theory (Section 8.4):

• Open question: Can $(r-2)$-rigidity strengthen the propagation lemma?
• Conjecture: Closure $C$ in $(r-2)$-rigidity matroid of $G\cup T$ gives at most $O(x)$ vertices in $T$ new neighbors

5. Generalization of Combinatorial Proof:

• This work's methods may apply to hypergraph bootstrap percolation 37
• Provides combinatorial alternative to algebraic approaches

In-Depth Evaluation

Strengths

1. Theoretical Depth:

• Completely resolves long-standing open problem, precise to constant factors
• Reveals essential new phenomena for $r \geq 5$ (non-nucleation mechanism)
• Establishes profound connection with Fuss-Catalan numbers

2. Technical Innovation:

• Tree Decomposition: Elegantly decomposes complex witness graphs into controllable structures
• $(r-2)^*$-BP: Creatively bridges edge dynamics and vertex dynamics
• Multi-Scale Analysis: Precise control at three scales: $O(\log n)$, $O(\log\log n)$, $O(1)$

3. Proof Robustness:

• Section 5's rough lower bound already answers Problem 3
• Section 6's refinement is modular improvement
• Methodology potentially applicable to other problems

4. Writing Quality:

• Section 2 clearly outlines challenges and ideas
• Technical details well-organized (three sections: preparation, rough, sharp)
• Figures and simulations enhance understanding

Weaknesses

1. Technical Complexity:

• Proof highly technical, especially Section 6
• Requires multiple auxiliary lemmas and refined estimates
• Some arguments (e.g., Lemma 6.5 proof) quite lengthy

2. Failure of Rigidity Approach:

• Authors attempted but failed to apply rigidity theory
• Insufficient explanation of failure reasons
• May limit method generalization

3. Simulation Limitations:

• Acknowledge $n=2000$ insufficient to observe true behavior
• No larger-scale numerical experiments provided
• Critical window numerical exploration missing

4. Barriers to Generalization:

• Heavily depends on special properties of $K_r$ (clique structure)
• Path to generalization to arbitrary strictly balanced graphs unclear
• Non-strictly-balanced case completely open

Impact

1. Theoretical Contribution:

• Resolves two open problems of Balogh-Bollobás-Morris
• Establishes new connection between graph bootstrap percolation and Fuss-Catalan numbers
• Provides complete theoretical picture for $r \geq 5$

2. Methodological Contribution:

• Tree decomposition technique potentially applicable to other bootstrap processes
• $(r-2)^*$-BP provides new analytical tool
• Refined combinatorial counting strategy has universal value

3. Practical Value:

• Strong theoretical focus, limited direct applications
• But provides mathematical foundation for network propagation, cascade failures
• Theoretical guidance for cellular automata design

4. Reproducibility:

• Proof completely self-contained
• Simulation code not public but methodology clearly described
• Theoretical results verifiable by readers

Applicable Scenarios

1. Direct Application:

• Analysis of $K_r$-percolation on random graphs ($r \geq 5$)
• Applications requiring precise threshold constants
• Subcritical edge expansion prediction

2. Methodological Application:

• Percolation of other strictly balanced graphs
• Hypergraph bootstrap percolation (e.g., 37)
• Propagation processes with tree-like witness structures

3. Theoretical Inspiration:

• Understanding combinatorial mechanisms of sharp thresholds
• Multi-scale analysis techniques
• Modified bootstrap processes as analytical tools

Key References

1. 1 Aizenman & Lebowitz (1988): First observation of Aizenman-Lebowitz property in bootstrap percolation
2. 8 Balogh, Bollobás & Morris (2012): Source of open problems directly resolved in this work
3. 15 Bollobás (1968): Origin of weak saturation concept
4. 32,33 Kalai (1984,1985): Connection between weak saturation and rigidity theory
5. 31 Janson et al. (2012): Detailed study of $r$-neighbor dynamics on random graphs
6. 37 Lubetzky & Peled (2023): Fuss-Catalan thresholds in hypergraphs, using algebraic methods
7. 40 Riedl (2012): Analysis of bootstrap percolation on trees, inspired Lemma 6.5 proof

Summary

This paper represents a major breakthrough in graph bootstrap percolation theory, completely resolving the sharp threshold problem for $K_r$-percolation when $r \geq 5$. Core innovations include: (1) tree decomposition technique systematically controlling witness graph complexity, (2) $(r-2)^*$-bootstrap percolation process cleverly analyzing zero-cost edge propagation, (3) profound connection with Fuss-Catalan numbers revealing combinatorial nature of threshold constants. The proof fully exploits strict balance of $K_r$ for $r \geq 5$, which is the essential distinction from the $r=4$ case. While technical complexity is high and generalization paths not entirely clear, the paper's methodological contributions and theoretical depth make it a landmark work in the field, establishing solid foundations for understanding more general graph bootstrap percolation and related propagation processes.