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

基本信息

  • 论文ID: 1611.10167
  • 标题: Thresholds for contagious sets in random graphs
  • 作者: Omer Angel, Brett Kolesnik
  • 分类: math.PR (概率论), math.CO (组合数学)
  • 发表时间: 2016年11月30日 (arXiv提交)
  • 论文链接: https://arxiv.org/abs/1611.10167

摘要

本文研究了Erdős-Rényi随机图Gn,pG_{n,p}上阈值为rr的bootstrap渗流过程。对于固定的r≥2r \geq 2，作者精确识别了边概率pp的阈值，超过该阈值后，高概率存在一个大小为rr的集合能够感染整个图。这一结果改进了Feige, Krivelevich和Reichman的工作，将阈值从乘法常数级别的界提升到渐近精确的结果。作为应用，作者还获得了K4K_4-bootstrap渗流阈值的上界，并猜想该界是渐近最优的。这些阈值与某些时变分支过程的存活概率密切相关，作者推导了这些存活概率的渐近公式。

研究背景与动机

研究问题

Bootstrap渗流是一个动态传播过程：给定图G=(V,E)G=(V,E)和初始感染集V0⊂VV_0 \subset V，在每个时间步，任何至少有rr个被感染邻居的顶点也会被感染并保持感染状态。核心问题是：

  1. 易感性阈值问题：在随机图Gn,pG_{n,p}中，边概率pp需要多大才能高概率保证存在一个大小为rr的集合（最小传染集）能够感染整个图？
  2. 图bootstrap渗流：对于K4K_4-bootstrap渗流（一种边添加规则），阈值是什么？

问题重要性

  • 理论意义：Bootstrap渗流是统计物理、计算机科学、神经网络和社会学中的重要模型，用于研究无序磁性系统、信息传播、意见扩散等现象
  • 数学挑战：随机图上的bootstrap渗流涉及复杂的依赖结构，精确阈值的确定需要深刻的组合和概率论技巧
  • 相变现象：该问题展现出清晰的相变行为——在临界阈值附近，系统从"几乎不可能全局感染"突变为"高概率全局感染"

现有方法局限性

Feige, Krivelevich和Reichman 24给出了易感性阈值的上下界，但只精确到乘法常数。具体而言，他们无法确定精确的常数因子αr\alpha_r。本文的主要贡献是识别出这个精确常数。

研究动机

作者发现易感性阈值与一类非齐次分支过程的存活概率密切相关。通过建立这种联系并精确分析分支过程，可以获得阈值的精确渐近表达式。

核心贡献

  1. 精确阈值识别（定理1.1）：对于rr-bootstrap渗流，证明了临界边概率为 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)) 其中α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渗流上界（定理1.2）：证明了 pc(n,K4)≤1+o(1)3nlog⁡np_c(n,K_4) \leq \frac{1+o(1)}{\sqrt{3n\log n}} 并猜想该界是渐近最优的
  3. 种子边阈值（定理1.4）：对于p=α/(nlog⁡n)p=\sqrt{\alpha/(n\log n)}，证明了α>1/3\alpha > 1/3时Gn,pG_{n,p}高概率包含种子边（seed edge）
  4. 分支过程存活概率（定理1.5）：对于相关的非齐次分支过程，推导出存活概率的渐近公式 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] 其中kr=((r−1)!ε)1/(r−1)k_r = \left(\frac{(r-1)!}{\varepsilon}\right)^{1/(r-1)}
  5. 方法创新：引入"无三角形易感图"（triangle-free susceptible graphs）的概念，通过限制到这类特殊图来建立传染集的近似独立性，从而使二阶矩方法可行

方法详解

任务定义

rr-bootstrap渗流：

  • 输入：图G=(V,E)G=(V,E)，初始感染集V0⊂VV_0 \subset V，阈值rr
  • 演化规则：Vt+1=Vt∪{v:∣N(v)∩Vt∣≥r}V_{t+1} = V_t \cup \{v : |N(v) \cap V_t| \geq r\}
  • 输出：最终感染集V∞=⟨V0,G⟩rV_\infty = \langle V_0, G \rangle_r

传染集（Contagious set）：如果⟨I,G⟩r=V\langle I, G \rangle_r = V，则称II为GG的传染集

易感性（Susceptibility）：如果图GG包含大小为rr的传染集（最小传染集），则称GG是易感的或rr-渗流的

临界概率：pc(n,r)=inf⁡{p>0:P(Gn,p易感)≥1/2}p_c(n,r) = \inf\{p > 0 : P(G_{n,p}\text{易感}) \geq 1/2\}

整体架构

论文的证明分为两个主要部分：

1. 下界证明（第2节）：证明α<αr\alpha < \alpha_r时不易感

核心思想：使用一阶矩方法（first moment method）证明当pp较小时，任何大小为rr的集合都只能感染O(log⁡n)O(\log n)个顶点。

关键步骤：

  • 建立递推关系计算最小易感图的数量mr(k,i)m_r(k,i)（大小为kk，顶层有ii个顶点）
  • 推导标准化量σr(k,i)\sigma_r(k,i)的上界（引理2.5）
  • 定义临界参数β∗(α)\beta^*(α)，它是方程的唯一正根： 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
  • 证明当α<αr\alpha < \alpha_r时，任何rr-渗流最多增长到(β∗(α)+δ)log⁡n(\beta^*(\alpha)+\delta)\log n个顶点（命题2.1）

2. 上界证明（第3节）：证明α>αr\alpha > \alpha_r时易感

核心思想：使用二阶矩方法证明存在传染集。主要挑战是传染集之间的依赖性。

创新策略：

  • 引入r^\hat{r}-渗流：限制到无三角形的易感子图，定义r^\hat{r}-渗流过程
  • 近似独立性（引理3.12）：利用Mantel定理（无三角形图的边密度至多1/2）证明不同r^\hat{r}-渗流之间近似独立
  • 下界估计：证明无三角形易感图的数量与一般易感图数量渐近相同（引理3.5）
  • 超临界增长：证明超过临界大小βr(α)log⁡n\beta_r(\alpha)\log n的渗流会继续增长到线性规模

技术细节

递推关系（方程2.1）

对于最小易感图数量： 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) 其中 ar(x,y)=(xr)−(x−yr)a_r(x,y) = \binom{x}{r} - \binom{x-y}{r} 表示顶层顶点可选择的连接方式数量。

标准化变换（方程2.3）

定义 σ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 这使得递推关系变为谱分析友好的形式。

无三角形图递推（方程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) 其中 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}\} 减去的项是可能创建三角形的连接方式。

近似独立性（引理3.12）

对于不相交的大小为rr的集合I≠I′I \neq I'，如果∣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}$$ 关键是利用Mantel定理（引理3.14）：无三角形图最多有$\lfloor v^2/4 \rfloor$条边。 ### 技术创新点 1. **分支过程联系**：首次建立易感性阈值与非齐次分支过程存活概率的精确联系。分支过程中第$n$个个体有$\text{Poi}(\binom{n}{r-1}\varepsilon)$个后代，其中$\varepsilon = np^r$ 2. **无三角形限制**：通过限制到无三角形易感图，巧妙地将依赖性问题转化为可处理的形式。这是因为无三角形图的稀疏性（Mantel定理）保证了不同渗流之间的"分离" 3. **双层分析**： - **亚临界阶段**（$k < \beta_r(\alpha)\log n$）：渗流可能存活但增长缓慢 - **超临界阶段**（$k > \beta^*(\alpha)\log n$）：渗流高概率继续增长到线性规模 4. **精细的组合估计**：对于不同顶层大小$i$的易感图，需要精细的下界估计（引理3.6），这对于分析超临界渗流至关重要 5. **多尺度耦合**：通过添加独立的随机图$G_0, G_1, \ldots$（边概率递减），证明大的易感子图可以感染整个图（定理1.1证明的最后部分） ## 实验设置 **注意**：这是一篇纯理论数学论文，不包含数值实验或数据集。所有结果都是通过严格的数学证明获得的。论文的"实验"是理论分析和渐近估计。 ### 理论验证方法 1. **渐近分析**：所有结果都在$n \to \infty$的渐近意义下成立 2. **概率估计**：使用"高概率"（with high probability, w.h.p.）表示概率趋于1当$n \to \infty$ 3. **精确常数**：通过解析计算确定精确的常数因子$\alpha_r$ ### 参数设置 - **阈值参数**：$r \geq 2$（固定） - **边概率**：$p = \left(\frac{\alpha}{n\log^{r-1}n}\right)^{1/r}$ - **临界常数**：$\alpha_r = (r-1)!\left(\frac{r-1}{r}\right)^{2(r-1)}$ - **分支过程参数**：$\varepsilon = np^r = \alpha/\log^{r-1}n$，$k_r = \left(\frac{(r-1)!}{\varepsilon}\right)^{1/(r-1)}$ ## 实验结果 ### 主要理论结果 #### 1. 精确阈值（定理1.1） **结果陈述**：对于$p = \left(\frac{\alpha}{n\log^{r-1}n}\right)^{1/r}$： - **超临界**（$\alpha > \alpha_r$）：$G_{n,p}$高概率易感 - **亚临界**（$\alpha < \alpha_r$）：$G_{n,p}$中任何大小为$r$的集合最多感染$\beta\log n$个顶点（某个$\beta = \beta(\alpha,r)$） **精确渐近**： $$p_c(n,r) = \left(\frac{\alpha_r}{n\log^{r-1}n}\right)^{1/r}(1+o(1))$$ **具体例子**： - $r=2$：$\alpha_2 = 1/4$，所以$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$，所以$p_c(n,3) \sim \left(\frac{16}{81n\log^2 n}\right)^{1/3}$ #### 2. $K_4$-bootstrap渗流（定理1.2） **结果**： $$p_c(n,K_4) \leq \frac{1+o(1)}{\sqrt{3n\log n}}$$ **猜想**：该上界是渐近最优的，即 $$p_c(n,K_4) = \frac{1+o(1)}{\sqrt{3n\log n}}$$ 这改进了Balogh, Bollobás和Morris [13]的结果$p_c(n,K_4) = \Theta(1/\sqrt{n\log n})$，给出了精确的常数因子$1/\sqrt{3}$。 #### 3. 种子边阈值（定理1.4） 对于$p = \sqrt{\alpha/(n\log n)}$： - $\alpha > 1/3$：$G_{n,p}$高概率包含种子边 - $\alpha < 1/3$：$G_{n,p}$高概率不包含种子边 **种子边定义**：边$(x_0,x_1)$是种子边，如果存在顶点排序使得$x_0,x_1$形成团，且每个后续顶点至少连接到前面的2个顶点。 #### 4. 分支过程存活概率（定理1.5） $$P(X_t > 0, \forall t) = \exp\left[-\frac{(r-1)^2}{r}k_r(1+o(1))\right]$$ 其中$k_r = \left(\frac{(r-1)!}{\varepsilon}\right)^{1/(r-1)}$大约是过程变为超临界的时间。 ### 关键引理结果 #### 引理2.5（易感图数量上界） $$m_r(k,i) \leq \frac{e^{-i-(r-2)k}}{\sqrt{i}}(k-r)!\left(\frac{k^{r-1}}{(r-1)!}\right)^k$$ 等价地，$\sigma_r(k,i) \leq i^{-1/2}e^{-i-(r-2)k}$ #### 引理3.5（无三角形易感图数量下界） $$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$$ 这表明限制到无三角形图只损失$e^{-o(k)}$因子，不影响主要渐近行为。 #### 引理3.6（带大顶层的易感图下界） 对于$\varepsilon \in (0, 1/(r+1))$和$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$$ 这对于分析超临界渗流的增长至关重要。 ### 分析与洞察 1. **相变的清晰性**：阈值$\alpha_r$两侧的行为完全不同——亚临界时只有对数级增长，超临界时有全局感染 2. **分支过程的角色**：临界常数$\alpha_r$恰好对应于相关分支过程从亚临界到超临界的转变点 3. **$\beta^*(\alpha)$的意义**： - 当$\alpha < \alpha_r$时，$\beta^*(\alpha) > \beta_r(\alpha)$，渗流在达到"本应"超临界的大小之前就停止了 - 当$\alpha = \alpha_r$时，$\beta^*(\alpha_r) = \beta_r(\alpha_r)$，恰好在临界点 - 当$\alpha > \alpha_r$时，$\beta^*(\alpha) < \beta_r(\alpha)$，渗流可以超越临界大小并继续增长 4. **种子边的特殊性**：对于$r=2$（$K_4$-bootstrap），种子边是最容易的感染方式。但对于$r>2$，种子不再是最容易的方式，因为$K_{r+2}$-bootstrap的阈值比种子阈值低得多 ## 相关工作 ### Bootstrap渗流的历史 1. **起源**：Chalupa, Leath和Reich [20]在1979年引入bootstrap渗流研究无序磁性系统 2. **格子和晶格上的研究**： - Aizenman和Lebowitz [3]：亚稳态效应 - Cerf和Cirillo [18]，Cerf和Manzo [19]：三维有限尺寸缩放 - Holroyd [33]，Gravner, Holroyd和Morris [32]：二维精确阈值 - Balogh, Bollobás和Morris [9, 10, 12]：所有维度的精确阈值 3. **随机图上的研究**： - Janson等人[36]：随机初始集的临界大小 - Balogh和Pittel [16]：随机正则图 - Amini [4]，Amini和Fountoulakis [5]：给定度序列的随机图 4. **最小传染集**： - Feige, Krivelevich和Reichman [24]：首次研究$G_{n,p}$上最小传染集的阈值，给出了$\Theta$界 - **本文**：改进为精确渐近结果 ### 图bootstrap渗流 1. **定义**：Bollobás [17]引入，规则是添加缺失一条边的$H$的副本 2. **$K_k$-bootstrap渗流**： - Balogh, Bollobás和Morris [13]：证明$p_c(n,K_4) = \Theta(1/\sqrt{n\log n})$ - **本文**：改进上界为$(1+o(1))/\sqrt{3n\log n}$ 3. **种子的作用**： - 引理1.3：如果有$K_{r+2}$-bootstrap的种子，则图会完全渗流 - 对于$K_4$，种子边是最简单的渗流方式（猜想） - 对于$K_k$（$k>4$），种子不是最简单的方式 ### 分支过程 非齐次分支过程在许多领域有应用，本文引入的特定模型（第$n$个个体有$\text{Poi}(\binom{n}{r-1}\varepsilon)$个后代）是新的，其存活概率的精确渐近公式（定理1.5）具有独立的理论兴趣。 ## 结论与讨论 ### 主要结论 1. **精确阈值识别**：首次给出$r$-bootstrap渗流易感性阈值的精确渐近表达式，确定了常数因子$\alpha_r = (r-1)!(r-1)^{2(r-1)}/r^{2(r-1)}$ 2. **方法论贡献**： - 建立了易感性阈值与非齐次分支过程的精确联系 - 引入无三角形限制来处理依赖性问题 - 发展了精细的组合计数技术 3. **应用**：改进了$K_4$-bootstrap渗流的阈值上界，猜想其为最优 ### 局限性 1. **$K_4$-bootstrap的下界**：论文只给出了上界$1/\sqrt{3n\log n}$，猜想其为精确阈值但未证明下界。对于$r>2$，种子不再是最简单的渗流方式，需要新的思路 2. **常数的复杂性**：虽然给出了精确的$\alpha_r$，但其表达式较复杂，不够直观 3. **非渐近行为**：所有结果都是渐近的（$n \to \infty$），对于有限$n$的行为没有给出精确估计 4. **推广性**：方法高度依赖于Erdős-Rényi随机图的特定结构，推广到其他随机图模型（如配置模型、几何随机图）可能需要新技术 ### 未来方向 1. **$K_4$-bootstrap下界**：证明或否定猜想$p_c(n,K_4) \sim 1/\sqrt{3n\log n}$ 2. **更一般的$K_k$-bootstrap**：对于$k>4$，确定精确阈值。论文指出这比种子阈值更难分析 3. **其他图类**：将方法推广到其他$H$-bootstrap渗流 4. **算法问题**：给定$G_{n,p}$，如何高效地找到最小传染集（如果存在）？ 5. **动态过程**：研究bootstrap渗流的时间演化，而不仅仅是最终状态 6. **亚临界行为的精细结构**：命题2.1表明亚临界时渗流增长到$\beta^*(\alpha)\log n$，能否精确刻画$\beta^*(\alpha)$附近的行为？ ## 深度评价 ### 优点 #### 1. 理论深度 - **精确结果**：从乘法常数级别的界提升到精确的渐近表达式，这在随机图理论中是重大进步 - **新联系**：首次建立易感性阈值与分支过程存活概率的精确联系，这种跨领域联系具有深刻的理论意义 - **完整性**：同时证明了上界和下界，给出了完整的相变图景 #### 2. 技术创新 - **无三角形限制**：这是处理依赖性问题的巧妙方法。通过Mantel定理，无三角形图的稀疏性自然地提供了"独立性" - **多尺度分析**：区分亚临界、临界和超临界三个阶段，每个阶段使用不同的技术 - **精细组合估计**：引理3.6对于带大顶层的易感图的下界估计技术难度很高，证明需要仔细的归纳和渐近分析 #### 3. 证明严谨性 - **完整证明**：所有主要结果都有详细证明，技术引理放在附录中 - **渐近分析的精细性**：对于$o(1)$项的处理非常仔细，明确指出哪些依赖于$n$，哪些依赖于其他参数 - **边界情况处理**：对于各种边界情况（如$i=k-r$，$k$接近临界大小等）都有仔细处理 #### 4. 写作质量 - **结构清晰**：论文组织良好，从问题定义到主要结果，再到详细证明，逻辑流畅 - **直观解释**：在技术证明之前通常给出直观解释（如第1.4节的证明概要） - **记号系统**：虽然记号较多，但定义清晰，使用一致 ### 不足 #### 1. 技术复杂性 - **证明长度**：主要证明非常长（第3节约20页），涉及大量技术细节，理解难度高 - **多层递推**：递推关系（如方程2.1，3.1）嵌套多层，追踪困难 - **常数计算**：$\alpha_r$的表达式虽然精确但不直观，没有给出简单的数值表或近似公式 #### 2. 结果的完整性 - **$K_4$-bootstrap下界缺失**：只有上界，猜想未证明 - **非渐近界**：没有给出有限$n$的显式界，不清楚渐近结果何时开始有效 - **$\beta^*(\alpha)$的隐式性**：$\beta^*(\alpha)$由隐式方程定义，没有显式表达式 #### 3. 推广性限制 - **模型特定性**：方法高度依赖于$G_{n,p}$的独立性和对称性 - **阈值参数固定**：只考虑固定的$r$，当$r$增长时（如$r=r(n)$）会发生什么？ - **一般图类**：对于非$K_k$的$H$-bootstrap渗流，方法是否适用不清楚 #### 4. 实用性 - **纯理论**：没有数值验证或模拟，无法评估渐近结果在实际规模（如$n=10^6$）下的准确性 - **算法缺失**：没有讨论如何实际找到传染集或验证易感性 - **应用有限**：虽然提到了应用领域，但没有具体的应用案例 ### 影响力 #### 对领域的贡献 1. **随机图理论**：为随机图上的动态过程提供了新的分析工具（无三角形限制技术） 2. **渗流理论**：深化了对bootstrap渗流相变的理解，特别是临界常数的精确值 3. **分支过程**：引入了新的非齐次分支过程模型并给出精确的存活概率公式 4. **组合数学**：发展了计数易感图的递推技术 #### 实用价值 - **理论指导**：为实际网络上的信息传播、疾病扩散等提供理论基准 - **算法设计**：虽然论文本身不讨论算法，但阈值的精确值可以指导传染集搜索算法的设计 - **参数选择**：在网络设计中，如果希望避免或促进全局传播，可以根据阈值选择连接密度 #### 可复现性 - **理论结果**：证明完整，原则上可以验证 - **数值验证**：虽然没有数值实验，但定理1.5（分支过程存活概率）可以通过蒙特卡洛模拟验证 - **代码缺失**：没有提供代码或数值实验，限制了实际应用 ### 适用场景 #### 理论研究 1. **随机图理论**：研究$G_{n,p}$上其他动态过程的阈值 2. **渗流理论**：推广到其他类型的bootstrap渗流或图类 3. **极值组合**：易感图的计数问题本身具有组合兴趣 #### 实际应用 1. **社交网络**：理解信息或行为在稀疏社交网络中的传播条件 2. **流行病学**：建模需要多次接触才感染的疾病传播 3. **网络可靠性**：分析级联故障的条件（反向视角：避免全局感染） 4. **神经网络**：理解神经元激活的阈值效应 #### 局限性 - **密度范围**：只适用于$p = \Theta(n^{-1/r}\log^{-(r-1)/r}n)$的稀疏图 - **齐次性**：假设所有顶点和边同质，实际网络通常是异质的 - **静态结构**：不考虑网络结构的动态变化 ## 参考文献（关键文献） 1. **[20] Chalupa, Leath, Reich (1979)**: Bootstrap percolation的原始论文 2. **[24] Feige, Krivelevich, Reichman (2016)**: 本文改进的前作，给出了$\Theta$界 3. **[13] Balogh, Bollobás, Morris (2012)**: Graph bootstrap percolation，本文应用的对象 4. **[36] Janson等人(2012)**: $G_{n,p}$上随机初始集的bootstrap渗流 5. **[23] Erdős, Rényi (1959)**: 随机图理论的奠基工作 6. **[39] Mantel (1907)**: Mantel定理，本文证明中的关键工具 7. **[44] Turán (1941)**: Turán定理，Mantel定理的推广 --- ## 总结 这是一篇高质量的理论数学论文，在随机图上的bootstrap渗流领域做出了重要贡献。主要成就是将易感性阈值从乘法常数级别的界提升到精确的渐近表达式，确定了常数因子$\alpha_r$。技术上的创新（特别是无三角形限制和分支过程联系）不仅解决了本文的问题，也为相关领域提供了新工具。 论文的主要局限在于技术复杂性高、部分结果（如$K_4$-bootstrap下界）未完成、缺乏数值验证。但考虑到问题的难度和结果的精确性，这些不足是可以接受的。 对于随机图理论和渗流理论的研究者，这是一篇必读文献。对于应用研究者，论文提供的阈值公式可以作为实际网络分析的理论基准，但需要注意模型假设（稀疏性、齐次性）的适用性。