Sharp Fuss-Catalan thresholds in graph bootstrap percolation

基本信息

• 论文ID: 2510.26724
• 标题: Sharp Fuss-Catalan thresholds in graph bootstrap percolation
• 作者: Zsolt Bartha, Brett Kolesnik, Gal Kronenberg, Yuval Peled
• 分类: math.PR (Probability Theory), math.CO (Combinatorics)
• 发表时间: 2025年10月30日提交至arXiv
• 论文链接: https://arxiv.org/abs/2510.26724

摘要

本文研究Erdős-Rényi随机图$G_{n,p}$上的图自举渗流(graph bootstrap percolation)。对于所有$r \geq 5$，作者精确定位了$K_r$-渗流的尖锐阈值$p_c \sim (\gamma n)^{-1/\lambda}$，解决了Balogh, Bollobás和Morris提出的公开问题。当$r=3$时对应经典的图连通性阈值，$r=4$的阈值已通过与统计物理中2-邻居动力学的联系得到解决。但当$r \geq 5$时，这种联系不再成立，过程表现出更丰富的行为。阈值$p_c$中的常数$\lambda=\lambda(r)$和$\gamma=\gamma(r)$由一类$\binom{r}{2}-1$元树状图决定，作者称之为$K_r$-树见证图(tree witness graphs)。这些图对应于$K_r$-动力学中添加新边的最有效方式，可用Fuss-Catalan数计数。此外，在亚临界设置下，作者确定了添加到$G_{n,p}$的边数的渐近行为，证明边密度仅增加一个可识别的常数因子。

研究背景与动机

问题背景

1. 图自举渗流的核心问题：给定模板图$H$和初始图$G \subseteq K_n$，$H$-自举渗流过程在每步添加一条新边$e$，前提是存在$K_n$中$H$的一个副本，其中$e$是唯一尚未添加到$G$的边。若$G$最终演化为完全图$K_n$，则称$G$弱$H$-饱和或$H$-渗流。
2. 阈值概率的重要性：对于Erdős-Rényi随机图$G_{n,p}$，临界阈值$p_c(n,H)$定义为使$P(\langle G_{n,p}\rangle_H = K_n) \geq 1/2$的最小$p$值。这是随机图理论的核心问题，推广了经典的图连通性阈值。
3. 已知结果的局限：
   • $r=3$: 经典结果$p_c(n,K_3) \sim \log n/n$（图连通性）
   • $r=4$: $p_c(n,K_4) \sim (3n\log n)^{-1/2}$，通过与2-邻居动力学的联系得到
   • $r \geq 5$: Balogh等人8仅确定了$p_c(n,K_r) = n^{-1/\lambda + o(1)}$，其中$\lambda = \frac{\binom{r}{2}-2}{r-2}$，精确到多对数因子

研究动机

1. 解决公开问题：Balogh等人在8中提出三个问题，本文以强形式解决了其中两个：
   • Problem 2: 确定哪些$H$具有尖锐阈值
   • Problem 3: 将$p_c(n,K_r)$精确到常数倍因子
2. $r \geq 5$的质变：当$r \geq 5$时，$K_r$变为严格平衡图(strictly balanced)，与$(r-2)$-邻居动力学的联系断裂，过程不再通过"成核"(nucleation)传播，而是表现出全新的行为模式。
3. 理论挑战：需要开发新的组合技术来分析见证图的结构，特别是控制"零成本"边的传播，这是本文的核心技术创新。

核心贡献

1. 尖锐阈值定理（定理1.1）：对于所有$r \geq 5$，证明了 $p_c(n,K_r) \sim (\gamma n)^{-1/\lambda}$ 其中$\gamma$由Fuss-Catalan数的渐近增长率$\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. 亚临界边扩张定理（定理1.2）：在亚临界区域$p = (\bar{\gamma}n)^{-1/\lambda}$（$\bar{\gamma} > \gamma$）下，证明了 $|E(\langle G_{n,p}\rangle_{K_r})| \sim \rho \cdot p\binom{n}{2}$ 其中$\rho > 1$是方程$\rho^{\binom{r}{2}-1} = \bar{\alpha}(\rho-1)$的最小根。
3. 树分解方法：引入见证图的树分解技术，将任意见证图分解为"坏部分"(bad part)和多个"树部分"(tree parts)，证明树部分数量为$O(\kappa)$，其中$\kappa$是总成本。
4. $(r-2)^*$-自举渗流过程：创新性地引入修改的$(r-2)$-邻居动力学，用于控制树部分内零成本边的传播，这是证明尖锐下界的关键工具。
5. 组合计数精确化：将见证图的计数从$A^\sigma\sigma!$（$A > \gamma$）精确到$\gamma^\sigma\sigma!\sigma^{O(\kappa^2)}$，这是获得尖锐常数的关键。

方法详解

任务定义

输入：Erdős-Rényi随机图$G_{n,p}$，模板图$H = K_r$（$r$-团）
输出：临界阈值$p_c(n,K_r)$使得$P(\langle G_{n,p}\rangle_{K_r} = K_n)$从接近0跃迁到接近1
约束：需要精确到常数因子，即确定$p_c \sim (\gamma n)^{-1/\lambda}$中的常数$\gamma$

核心概念体系

1. 见证图(Witness Graph)

对于$K_r$-动力学中添加的每条边$e$，存在一个见证图$W(e) \subseteq G$，使得$e \in E(\langle W(e)\rangle_{K_r})$。见证图通过见证图算法(WGA)递归定义：

• 若$e \in E_0$（初始边），则$W(e) = e$
• 否则，选择$K_r$的副本$H(e)$满足$E(H(e)\setminus e) \subset \bigcup_{s<t}E_s$，令$W(e) = \bigcup_{f \in E(H(e)\setminus e)}W(f)$

2. $K_r$-树见证图(Tree Witness Graph, TWG)

TWG是边数最少的见证图，递归定义为：

• 基础情况：单边$e$是0-TWG
• 递归构造：$k$-TWG通过以下方式获得：
  • 取$(k-1)$-TWG $T'$
  • 移除其中一条边$e'$
  • 用包含$e'$的$K_r$副本$H'$（移除$e'$后）替换

关键性质（引理3.6）：

• 顶点数：$v(T) = (r-2)k + 2$
• 边数：$e(T) = \lambda(r-2)k + 1$，其中$\lambda = \frac{\binom{r}{2}-2}{r-2}$
• 树状结构：可用$\binom{r}{2}-1$元树表示

3. Fuss-Catalan数的联系

$k$-TWG的数量为（引理3.8）： $t(k) = \frac{((r-2)k)!}{(r-2)!^k} \text{FC}_{\binom{r}{2}-2}(k)$ 其中Fuss-Catalan数$\text{FC}_d(k) = \frac{1}{dk+1}\binom{(d+1)k}{k}$，渐近增长率为$\alpha_d = \frac{(d+1)^{d+1}}{d^d}$。

上界证明策略（第3节）

关键思想

在超临界区域$p = ((1+\epsilon)\gamma n)^{-1/\lambda}$，证明高概率下所有边都能通过对数阶TWG添加。

技术步骤

1. 平衡TWG的期望计数（引理3.12）： 对于固定边$e$，平衡$k$-TWG（所有主分支阶数相等）的数量$B_k^{(e)}$满足： $\mathbb{E}(B_k^{(e)}) \sim \phi' \frac{(1+\epsilon)^{(r-2)k}}{k^{3((\binom{r}{2}-1)/2)}}p$ 当$k = \beta\log n$（$\beta$足够大）时，期望值$\gg n^c$。

2. 部分TWG的结构引理（引理3.16）： 对于TWG $T$的真子图$S$，定义三个关键参数：

• 边效率：$\mathcal{E}(S) = \lambda\sigma(S) - e(S) \geq 0$
• 树内缺陷：$\mathcal{D}(S,T) = |P| \leq c\mathcal{E}(S) + 2$
• 树可扩展性：$\mathcal{T}(S) \leq c\mathcal{E}(S)$

其中$\sigma(S) = |V(S)\setminus e|$是非目标边端点的顶点数。

3. Janson不等式应用： 计算方差项$\Delta = \sum_{T_1 \sim T_2}P(T_1,T_2 \subset G_{n,p})$，关键是利用：

• 若$S = T_1 \cap T_2$有$\mathcal{E}(S) > 0$，则$p^{\mathcal{E}(S)}$项提供足够衰减
• 若$\mathcal{E}(S) = 0$，则$S$通过移除分支获得，利用平衡性得$\sigma(S) \geq ck$

结论：$\Delta/\mu^2 \ll (k/n)^c$，Janson不等式给出$P(B_k^{(e)} = 0) \ll n^{-2}$，联合界证明全渗流。

下界证明策略（第5-6节）

第一阶段：粗糙下界（第5节）

证明$p_c = \Omega(n^{-1/\lambda})$。

1. 树分解构造： 对于任意见证图$W$，在红边算法(REA)的每步将组件$C$分解为：

• 坏部分$B$（可能为空）
• 树部分$T_1,\ldots,T_k$（每个是$K_r$-树）

满足性质：

• 若$B = \emptyset$，则$k=1$且$C$是树组件
• 若$B \neq \emptyset$，每个$T_i$与$B$交于单边（称为基边），树部分两两边不交

2. 复杂度界（引理5.7）： 定义树数$\tau(C)$为REA中被"妥协"（添加到坏部分）的树部分数，证明： $\tau(C) = O(\kappa(C))$ 其中$\kappa(C)$是成本（昂贵步骤中涉及的顶点数）。

3. 组合计数（引理5.10）： 大小为$\sigma$、成本为$\kappa$的见证图数量至多： $A^\sigma \cdot \sigma! \cdot \sigma^{O(\kappa)}$ 其中$A > \gamma$是某常数。

4. 期望计算： 结合引理4.9（$\chi(W) \geq \xi\kappa(W)$）和上述计数，对于$p = (\epsilon/n)^{1/\lambda}$（$\epsilon < 1/\gamma$），见证图的期望数量： $\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$

第二阶段：尖锐下界（第6节）

证明$p_c \sim (\gamma n)^{-1/\lambda}$。

核心挑战：需要将计数从$A^\sigma$改进到$\gamma^\sigma$，差距在于非TWG的树组件贡献。

关键创新1：$(r-2)^*$-自举渗流（定义6.2）： 在$K_r$-树$T$上定义修改的$(r-2)$-邻居过程，允许特殊步骤：

• 通常步骤：$\geq r-2$个感染邻居的顶点被感染
• 特殊步骤：对于内部边$e$，若两个包含$e$的$K_r$副本$H_i,H_j$中，$H_i$有$r-4$个感染顶点，$H_j$有1个感染顶点（都不在$e$中），则感染$e$的一个顶点

关键创新2：比较引理（引理6.3）： 设$T$是$K_r$-树，$G$是图，$S = V(G)\cap V(T)$。则： $\langle G \cup T\rangle_{K_r} \subset Q \cup T$ 其中$Q$是$V(G) \cup \langle S;T\rangle^*$上的团，$\langle S;T\rangle^*$是$(r-2)^*$-BP的最终感染集。

关键创新3：扩张引理（引理6.5）： $(r-2)^*$-BP过程至多线性扩张：$|\langle S;T\rangle^*| = O(|S|)$。

证明技巧：

• 追踪感染时的邻居数，定义$k$-步（恰有$k$条边连接到已感染顶点）
• 通过探索过程（逐个揭示$K_r$副本）建立不等式系统
• 利用$r \geq 5$的严格平衡性质确保特殊步骤被后续通常步骤"补偿"

传播引理（引理6.7）： 若$|V(T)\cap V(G)| = x$，则$K_r$-动力学在$G\cup T$上使用$T$中至多$O(x)$条边。

改进的组合计数（引理6.10）： 利用引理6.8（每个最大树部分至多有$O(\kappa)$个目标边），证明： $\text{见证图数量} \leq \gamma^\sigma \cdot \sigma! \cdot \sigma^{O(\kappa^2)}$

最终论证： 对于$p = ((1-\epsilon)\gamma n)^{-1/\lambda}$，期望数量： $\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$

技术创新点

1. 树分解的创新性设计

• 动态维护性质：在REA的每步动态更新分解，保持三个关键性质
• 坏树步的处理：将辅助树$T$添加到坏部分而非作为树部分，这是控制树部分数量的关键
• 与成本的紧密关联：证明$\omega(W) = O(\kappa(W))$和$\sum|V(T_i)| = \sigma + O(\kappa)$

2. $(r-2)^*$-BP的巧妙设计

• 优先级机制：优先使用通常步骤，仅在必要时使用特殊步骤
• 与$K_r$-动力学的对应：特殊步骤精确捕捉边传播通过"铰链"(hinge)的条件
• 线性扩张的证明：通过精细的计数论证，利用$r \geq 5$确保特殊步骤的成本被后续步骤吸收

3. 严格平衡性的深刻应用

定义（定义3.17）：图$H$严格平衡若对所有$3 \leq v(F) < v(H)$的子图$F$： $\frac{e(F)-1}{v(F)-2} < \lambda(H) = \frac{e(H)-2}{v(H)-2}$

关键应用：

• 引理3.20：控制部分TWG内叶子的边效率
• 声明5.3：证明IntR步不会在树部分间传播
• 引理6.3的证明：确保矛盾情况不会发生

4. 多尺度分析

• 对数尺度：TWG的阶数$k = O(\log n)$
• 双对数尺度：成本$\kappa = O(\log\log n)$
• 常数尺度：树部分的目标边数$O(\kappa)$

实验设置

模拟研究（第8.2节）

参数设置：

• 顶点数：$n = 2000$
• 模板图：$K_5$（$r=5$）
• 三个阶段：亚临界、临界附近、超临界

可视化方法：

• 矩阵表示：点$(i,j)$表示边$\{v_i,v_j\}$
• 颜色编码：深蓝（初始边）→黄色（最后添加），白色（未添加）
• 顶点排序：偏向早期添加边的顶点

观察结果：

1. 亚临界：边密度仅增加常数因子，局部化在100个顶点
2. 超临界：早期阶段缓慢增长，随后"爆炸"式全渗流
3. 轮数：亚临界4轮，超临界15轮

局限性讨论：

• $L = (np^{r-2})^{-1/(r-3)} \approx 1.6$对于$n=2000,r=5$太小
• 实际观察到的是3-邻居动力学主导的行为
• 需要$n$极大才能观察到真正的$r \geq 5$行为（"慢老化"现象）

实验结果

理论结果验证

定理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$

定理1.2的具体形式（$r=5$，$\bar{\gamma} = 1.2$）：

• $\bar{\alpha} = 6 \times 1.2^3 \approx 10.368$
• $\rho$满足$\rho^9 = 10.368(\rho-1)$，数值解$\rho \approx 1.52$
• 边密度增加约52%

数值验证（图1）

亚临界情况（图1a）：

• 初始边数：$\approx p\binom{n}{2} \approx 1000$
• 最终边数：$\approx 1.5 \times 1000 = 1500$
• 与理论预测$\rho \approx 1.52$吻合

超临界情况（图1c）：

• 所有$\binom{2000}{2} \approx 2\times 10^6$条边最终添加
• 呈现两阶段：缓慢增长（深蓝到绿色）+ 爆炸式完成（橙到黄）

关键发现

1. 阈值的尖锐性：从亚临界到超临界，渗流概率从接近0跃迁到接近1，窗口宽度为$o(p_c)$
2. TWG的主导地位：
   • 超临界：几乎所有边通过对数阶TWG添加
   • 亚临界：$\rho$因子完全由TWG贡献决定
3. 成本的作用：
   • 非TWG见证图的成本$\kappa \geq 1$提供额外因子$p^{\xi\kappa}$
   • 这足以抵消其数量增加（从$\gamma^\sigma$到$\gamma^\sigma\sigma^{O(\kappa^2)}$）
4. $r \geq 5$的质变：
   • 不存在中间尺度的渗流子图（$1 \ll k \ll L$）
   • 与$r=4$的成核机制根本不同

相关工作

自举渗流的历史脉络

1. 经典顶点自举渗流：

• Chalupa等18：统计物理中的起源
• Aizenman-Lebowitz1：$\mathbb{Z}^d$上的亚稳态性质
• Holroyd30：二维尖锐亚稳态阈值
• Balogh等7：所有维度的尖锐阈值
• Balister等6：单调细胞自动机的普适性猜想

2. 随机图上的$r$-邻居动力学：

• Janson等31：$G_{n,p}$上的详细研究
• 关键区别：顶点感染 vs. 边感染

3. 图自举渗流：

• Bollobás15：弱饱和的引入，确定$r \leq 6$的最小边数
• Alon2, Frankl23, Kalai32,33, Lovász36：推广到所有$r$
• Balogh等9：超图推广
• Balogh等8：随机图上的阈值，本文的直接前身

本文的定位

相对于8的进展：

• 8的结果：$p_c(n,K_r) = n^{-1/\lambda+o(1)}$（多对数精度）
• 本文：$p_c(n,K_r) \sim (\gamma n)^{-1/\lambda}$（常数精度）
• 解决Problem 2（尖锐性）和Problem 3（常数因子）

技术对比：

• 8：使用$K_r$-梯子图 + Aizenman-Lebowitz性质
• 本文：树分解 + $(r-2)^*$-BP + Fuss-Catalan计数

与其他模板图$H$的关系：

• Korándi-Sudakov35等：$G_{n,p}$中的饱和问题
• Bayraktar-Chakraborty12, Bidgoli等13：$K_{r,s}$-渗流
• 一般$H$的理解仍然广泛开放（Problem 1 in 8）

跨领域联系

超图自举渗流：

• Lubetzky-Peled37：堆叠三角剖分的Fuss-Catalan型阈值
• 使用外部代数移位，与本文的组合方法互补

刚性理论：

• Kalai32：弱饱和与$(r-2)$-刚性的联系
• 本文尝试但未成功应用刚性理论（第8.4节）
• 开放问题：能否用刚性理论加强传播引理？

结论与讨论

主要结论

1. 完全解决$r \geq 5$的阈值问题： $p_c(n,K_r) = \frac{1}{\gamma n^{1/\lambda}}(1+o(1))$ 其中$\gamma,\lambda$由Fuss-Catalan数的渐近性质唯一确定。
2. 亚临界边扩张的精确刻画： 边密度增加因子$\rho$由生成函数方程$\rho^{\binom{r}{2}-1} = \bar{\alpha}(\rho-1)$确定。
3. 揭示$r \geq 5$的新机制：
   • 不通过成核传播
   • TWG主导渗流过程
   • 严格平衡性是关键

局限性

1. 临界窗口未确定：
   • 第二阶项未知
   • 临界窗口宽度$\omega(n)$未确定
   • 临界行为的精细结构不清楚
2. "临界液滴"未识别：
   • 理论预测尺度$L = n^{(r-4)/(r^2-r-4)+o(1)}$
   • 但证明未直接构造这样的子图
   • 与成核机制的关系不明
3. 模拟的局限性：
   • 需要$n$极大才能观察真实行为（慢老化）
   • 当前模拟主要显示$(r-2)$-邻居动力学
4. 方法的适用范围：
   • 严重依赖$r \geq 5$（严格平衡性）
   • 推广到一般$H$需要新思想
   • 刚性理论方法未成功

未来方向

1. 临界现象的精细理解（第8.1节）：

• 确定临界窗口宽度
• 刻画$G(n,m)$演化中的"爆炸"步
• 识别尺度$L$的临界液滴

2. 推广到严格平衡图（第8.3节）：

• 猜想：所有严格平衡$H$满足$p_c = \Theta(n^{-1/\lambda})$
• 上界已由10证明
• 下界需要推广树分解和传播引理
• 关键：利用额外因子$p^{\xi\kappa}$（$\xi > 0$）

3. 一般模板图$H$（Problem 1 in 8）：

• 确定$p_c(n,H)$对所有$H$
• 判定尖锐性条件
• 平衡但非严格平衡图的行为

4. 刚性理论的应用（第8.4节）：

• 开放问题：能否用$(r-2)$-刚性加强传播引理？
• 猜想：闭包$C$在$G\cup T$的$(r-2)$-刚性拟阵中至多使$T$中$O(x)$个顶点获得新邻居

5. 组合证明的推广：

• 本文方法可能适用于超图自举渗流37
• 提供代数方法的组合替代

深度评价

优点

1. 理论深度：

• 完全解决长期公开问题，精确到常数因子
• 揭示$r \geq 5$的本质新现象（非成核机制）
• 建立与Fuss-Catalan数的深刻联系

2. 技术创新：

• 树分解：优雅地将复杂见证图分解为可控结构
• $(r-2)^*$-BP：创造性地桥接边动力学和顶点动力学
• 多尺度分析：$O(\log n)$, $O(\log\log n)$, $O(1)$三个尺度的精细控制

3. 证明的鲁棒性：

• 第5节的粗糙下界已经回答Problem 3
• 第6节的精细化是模块化的改进
• 方法论对其他问题有潜在适用性

4. 写作质量：

• 第2节的概览清晰阐述挑战和思想
• 技术细节组织良好（分三节：准备、粗糙、尖锐）
• 图示和模拟增强理解

不足

1. 技术复杂度：

• 证明高度技术化，特别是第6节
• 需要多个辅助引理和精细估计
• 部分论证（如引理6.5的证明）较为冗长

2. 刚性方法的失败：

• 作者尝试但未能应用刚性理论
• 未充分解释失败原因
• 可能限制方法的推广

3. 模拟的有限性：

• 承认$n=2000$不足以观察真实行为
• 未提供更大规模的数值实验
• 临界窗口的数值探索缺失

4. 一般化的障碍：

• 严重依赖$K_r$的特殊性质（团结构）
• 推广到一般严格平衡图的路径不明确
• 非严格平衡情况完全开放

影响力

1. 理论贡献：

• 解决Balogh-Bollobás-Morris的两个公开问题
• 建立图自举渗流与Fuss-Catalan数的新联系
• 为$r \geq 5$提供完整理论图景

2. 方法论贡献：

• 树分解技术可能适用于其他自举过程
• $(r-2)^*$-BP提供新的分析工具
• 组合计数的精细化策略有普遍价值

3. 实用价值：

• 理论性强，直接应用有限
• 但为网络传播、级联失效等提供数学基础
• 细胞自动机设计的理论指导

4. 可复现性：

• 证明完全自包含
• 模拟代码未公开但方法描述清楚
• 理论结果可由读者验证

适用场景

1. 直接适用：

• 随机图上的$K_r$-渗流分析（$r \geq 5$）
• 需要精确阈值常数的应用
• 亚临界边扩张的预测

2. 方法适用：

• 其他严格平衡图的渗流
• 超图自举渗流（如37）
• 具有树状见证结构的传播过程

3. 理论启发：

• 理解尖锐阈值的组合机制
• 多尺度分析技术
• 修改的自举过程作为分析工具

参考文献（关键引用）

1. 1 Aizenman & Lebowitz (1988): 首次观察自举渗流的Aizenman-Lebowitz性质
2. 8 Balogh, Bollobás & Morris (2012): 本文直接解决的公开问题来源
3. 15 Bollobás (1968): 弱饱和概念的起源
4. 32,33 Kalai (1984,1985): 弱饱和与刚性理论的联系
5. 31 Janson等 (2012): 随机图上$r$-邻居动力学的详细研究
6. 37 Lubetzky & Peled (2023): 超图中的Fuss-Catalan阈值，使用代数方法
7. 40 Riedl (2012): 树上自举渗流的分析，启发了本文引理6.5的证明

总结

本文是图自举渗流理论的重大突破，完全解决了$r \geq 5$情况下$K_r$-渗流的尖锐阈值问题。核心创新在于：(1) 树分解技术系统地控制见证图的复杂度，(2) $(r-2)^*$-自举渗流过程巧妙地分析零成本边的传播，(3) 与Fuss-Catalan数的深刻联系揭示了阈值常数的组合本质。证明充分利用了$r \geq 5$时$K_r$的严格平衡性，这是与$r=4$情况的本质区别。虽然技术复杂度较高且推广路径不完全清晰，但本文的方法论贡献和理论深度使其成为该领域的里程碑工作，为理解更一般的图自举渗流和相关传播过程奠定了坚实基础。