2025-11-17T08:22:14.076517

Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree

Diskin, Krivelevich
We provide sufficient conditions for a regular graph $G$ of growing degree $d$, guaranteeing a phase transition in its random subgraph $G_p$ similar to that of $G(n,p)$ when $p\cdot d\approx 1$. These conditions capture several well-studied graphs, such as (percolation on) the complete graph $K_n$, the binary hypercube $Q^d$, $d$-regular expanders, and random $d$-regular graphs. In particular, this serves as a unified proof for these (and other) cases. Suppose that $G$ is a $d$-regular graph on $n$ vertices, with $d=ω(1)$. Let $ε>0$ be a small constant, and let $p=\frac{1+ε}{d}$. Let $y(ε)$ be the survival probability of a Galton-Watson tree with offspring distribution Po$(1+ε)$. We show that if $G$ satisfies a (very) mild edge expansion requirement, and if one has fairly good control on the expansion of small sets in $G$, then typically the percolated random subgraph $G_p$ contains a unique giant component of asymptotic order $y(ε)n$, and all the other components in $G_p$ are of order $O(\log n/ε^2)$. We also show that this result is tight, in the sense that if one asks for a slightly weaker control on the expansion of small sets in $G$, then there are $d$-regular graphs $G$ on $n$ vertices, where typically the second largest component is of order $Ω(d\log (n/d))=ω(\log n)$. This is the first of a two-part sequence of papers. In the subsequent work, we consider supercritical percolation on regular graphs of constant degree, and establish similar sufficient (and essentially tight) conditions in that setting.
academic

Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree

基本信息

  • 论文ID: 2408.04597
  • 标题: Components, large and small, are as they should be I: supercritical percolation on regular graphs of growing degree
  • 作者: Sahar Diskin, Michael Krivelevich (Tel Aviv University)
  • 分类: math.CO (组合数学), math.PR (概率论)
  • 发表时间: 2024年8月提交，2025年11月修订版
  • 论文链接: https://arxiv.org/abs/2408.04597

摘要

本文针对度数增长的d-正则图G，提供了充分条件以保证其随机子图Gp在p·d≈1时出现类似于经典Erdős-Rényi随机图G(n,p)的相变现象。当G是n个顶点的d-正则图（d=ω(1)），p=(1+ε)/d时，若G满足非常温和的边扩张要求和对小集合扩张的良好控制，则典型地Gp包含唯一的巨连通分量，其阶为y(ε)n（y(ε)是参数为Po(1+ε)的Galton-Watson树的存活概率），而所有其他连通分量的阶为O(log n/ε²)。作者还证明该结果是紧的：若对小集合扩张的控制稍弱，则存在d-正则图使得第二大连通分量的阶为Ω(d log(n/d))=ω(log n)。

研究背景与动机

研究问题

本文研究正则图上的超临界渗流（supercritical percolation）问题：给定宿主图G和概率p∈0,1，通过独立地以概率p保留G的每条边来获得渗流随机子图Gp。核心问题是：什么样的正则图G能够展现Erdős-Rényi连通分量现象（ERCP），即在超临界阶段p=(1+ε)/d时，出现唯一的巨连通分量且其余连通分量都是对数阶的？

问题重要性

  1. 统一理解相变现象：Erdős-Rényi在1960年证明了经典随机图G(n,p)在p·n≈1时的相变现象。该现象已在多种特殊图上被独立证明（完全图、超立方体、伪随机图等），但证明方法各异。本文旨在提供统一框架。
  2. 刻画普适性类：识别哪些图结构性质决定了ERCP的出现，有助于理解渗流理论中的普适性（universality）。
  3. 理论完备性：已知某些图（如不连通的团的并）不展现ERCP，因此需要精确刻画边界条件。

现有方法局限性

  • 特殊结构依赖：超立方体的证明依赖其乘积结构和Harper等周不等式；伪随机图的证明依赖扩张混合引理
  • 证明技术分散：不同图类需要完全不同的证明技术，缺乏统一视角
  • 条件不明确：对于一般正则图，何种扩张性质足以保证ERCP尚不清楚
  • 紧性未知：现有充分条件是否必要尚未确定

研究动机

作者旨在通过纯粹的扩张性质（而非特殊结构）来刻画ERCP，提供统一的证明框架，并通过构造反例证明条件的紧性。

核心贡献

  1. 统一充分条件框架：提出了基于扩张性质的充分条件（定理1），涵盖度数d≥log^α n的情况，统一证明了完全图、超立方体、d-正则扩张图、随机d-正则图等多种图类的ERCP。
  2. 三个主要定理：
    • 定理1（d≥log^α n）：要求全局温和边扩张(P1)、小集合顶点扩张(P2)、小集合近最优边扩张(P3)
    • 定理3（d≥10log n/ε）：移除(P2)，仅需(P1)和加强的(P2')
    • 定理4（d=ω(1)）：移除(P2)和度数下界，但需要加强(P3)至更大集合
  3. 紧性结果（定理2）：构造反例证明小集合扩张条件(P3)在常数因子意义上是紧的——若仅对大小≤εd log(n/d)/(100c₁)的集合要求近最优边扩张，则存在图使得第二大连通分量为Ω(d log(n/d))。
  4. 新技术创新：
    • 证明大连通分量"处处稠密"（everywhere dense）
    • 双曝光/撒点（double-exposure/sprinkling）技术
    • 连通分量大小的间隙引理（gap lemma）
  5. 统一证明范式：提供了不依赖特殊结构（如乘积结构或伪随机性）的纯扩张性证明。

方法详解

任务定义

输入：d-正则图G=(V,E)，n=|V|，度数d=ω(1)，渗流概率p=(1+ε)/d（ε>0为小常数）
输出：证明Gp高概率地（whp）具有以下性质：

  • 存在唯一巨连通分量L₁，|L₁|=(1+o(1))y(ε)n
  • 所有其他连通分量的阶为O(log n/ε²)

其中y(ε)∈(0,1)是方程y=1-exp{-(1+ε)y}的唯一解，即Po(1+ε)分支过程的存活概率。

核心假设条件

定理1要求G满足：

(P1) 全局边扩张：对所有U⊆V，|U|≤n/2，有e(U,U^C)≥c₁|U|（c₁>0为常数）

(P2) 小集合顶点扩张：对所有U⊆V，|U|≤c₂log n，有|N(U)|≥c₃d|U|（c₂,c₃>0为常数）

(P3) 小集合近最优边扩张：对所有U⊆V，|U|≤Cd log n，有e(U,U^C)≥(1-ε³)d|U|（C为充分大常数）

证明架构

整体策略

采用双曝光技术：设p₂=ε³/d，选择p₁使得(1-p₁)(1-p₂)=1-p，则Gp与Gp₁∪Gp₂同分布。证明分为四个主要步骤：

步骤1：大连通分量处处稠密（第3.1节）

  • 定义"大连通分量"：VL(H)={v: |C_H(v)|≥7log n/ε²}
  • 目标：证明whp每个顶点v在距离1+log_d log n内有Ω(d log n)个VL(Gp)中的顶点

步骤2：连通分量大小间隙（引理3.4）

  • 证明whp不存在阶在7log n/ε², Cd log n内的连通分量
  • 这需要精细的计数和概率估计

步骤3：大连通分量合并（第3.2节，引理3.5）

  • 证明whp所有Gp₁中的大连通分量在撒点Gp₂后合并为单一连通分量
  • 关键：构造足够多的顶点不相交路径

步骤4：体积集中（第3.3节，引理3.8）

  • 证明大连通分量中的顶点总数集中在y(ε)n附近

技术细节

引理3.1：固定集合的连通分量行为

对|S|=c'd log n的集合S（c'=c₂c₃^(1+1/α)），证明：

  • (a) 不存在U⊆S使得∪{u∈U}C(u)的阶在c'd log n/ε³, 2c'd log n/ε³
  • (b) 不存在大子集U⊆S（|U|≥(1-ε²)c'd log n）使得∪{u∈U}C(u)的阶≤Cd log n

证明技巧：

  • 使用森林计数（引理2.3）：k个顶点的树至多(ed)^(k-1)种
  • 利用(P3)：边界至少有(1-ε³)kd条边必须不在Gp中
  • 概率估计：(edp)^(k-1)(1-p)^((1-ε³)kd) ≤ exp{-ε²k/4}

引理3.3：处处稠密性

证明whp每个v∈V在距离≤1+log_d log n内有≥ε²c'd log n个VL(Gp)中的顶点。

证明路径：

  1. 由(P2)，|B_G(v, log_d log n)|≥c₂c₃^(log_d log n) log n≥c₂c₃^(1/α) log n
  2. 由(P2)再次应用，|B_G(v, 1+log_d log n)|≥c₃d·c₂c₃^(1/α) log n=c'd log n
  3. 对Sv⊆B_G(v, 1+log_d log n)，|Sv|=c'd log n，由推论3.2得|Sv∩VL(Gp)|≥ε²c'd log n
  4. 联合界over所有v完成证明

引理3.5：大连通分量合并

设W=VL(Gp₁)，对W的任意连通分量尊重的划分W=A⊔B，需在Gp₂中找到A到B的路径。

构造过程（假设|A|≤|B|）：

  1. 定义A₀=A, B₀=B，递归构造Ai, Bi（i=1,...,r，r=1+log_d log n）：
    • Ai包含到Ai₋₁有≥ε²c'd/(5r)个邻居的顶点
    • Bi类似定义
  2. 声称3.6：V=A'⊔B'，其中A'=∪Ai, B'=∪Bi
  3. 在Gp₂中暴露A'到B'的边，由(P1)和引理2.4得匹配M，|M|≥ε⁶c₁|A|/d
  4. 递归地将M的端点通过Gp₂中的路径延伸到A₀=A
  5. 类似地从B'延伸到B，最终连接A和B

概率估计：

  • 每步失败概率≤exp{-ε⁸c'|Mi,A'|/(5r)}
  • 最终路径数≥(ε⁸c'c₁/(5r))^(r+1)|A|/d
  • 划分数≤n^(|A|/(Cd log n))
  • 联合界：≤2n·exp{-(ε⁸c'c₁/(7r))^(2r+1)C log n}=o(1)

引理3.4：间隙引理

证明whp不存在连通集K，|K|∈7log n/ε², Cd log n且E_{Gp₁}(K,K^C)=∅。

关键估计：

  • 阶为k的树T：至多n(ed)^(k-1)种
  • 由(P3)：e(V(T), V\V(T))≥(1-ε³)kd
  • P所有边在Gp且边界无边在Gp₁≤n(edp)^(k-1)exp{-p₁(1-ε³)dk}
  • ≤n exp{k(1+log(1+ε)-(1+ε-3ε³))}≤n exp{-ε²k/3}=o(1/n)

引理3.8：体积集中

设W为Gp中阶≥14log n/ε²的连通分量的顶点集。

期望计算：

  • 固定v，通过BFS探索，被Bin(d,p)分支过程随机支配
  • P|C_(v)|≥14log n/ε²≤(1+o(1))y(ε)（上界）
  • 修改BFS在√d步停止，被Bin(d-√d,p)支配
  • P|C_(v)|≥√d≥(1-o(1))y(ε)（下界）
  • 由引理3.7，EW=(1+o(1))y(ε)n

集中性：

  • 边暴露鞅，每条边改变|W|至多28log n/ε²
  • 由Azuma-Hoeffding（引理2.2）：P||W|-EW|≥n^(2/3)≤2exp{-n^(4/3)/(O(ndp·log²n/ε⁴))}=o(1)

技术创新点

  1. 处处稠密性的新证明：不依赖乘积结构，纯粹通过球增长和顶点扩张建立
  2. 路径构造的递归策略：在撒点概率p₂=ε³/d下，长度r=O(log_d log n)的路径出现概率p₂^r可能很小，通过递归匹配和集合构造Ai巧妙解决
  3. 间隙引理的精确常数：7log n/ε²到Cd log n的间隙对于后续论证至关重要，常数选择与p₂=ε³/d紧密相关（与log(1+x)的泰勒展开有关）
  4. 紧性构造（定理2）：通过c'₁-正则图H（满足全局扩张）加上颜色类内的(n',d',λ')-图构造，使得颜色类在Gp中被孤立

实验设置

本文为纯理论数学论文，不包含计算实验。所有结果均为严格的数学证明。

应用实例（作为"验证"）

论文展示了定理1及其变体如何恢复已知结果：

  1. 完全图Kn：由定理3恢复Erdős-Rényi经典结果
  2. 伪随机(n,d,λ)-图（λ=o(d)）：由扩张混合引理验证(P3)，定理3/4适用
  3. 随机d-正则图：whp是(n,d,Ω(√d))-图，满足所有条件
  4. 超立方体Qd：Harper等周不等式给出e(U,U^C)≥|U|(d-log₂|U|)，满足(P1)和(P3)；小集合顶点扩张由Harper结果给出
  5. 高维乘积图：通过Harper型不等式满足条件
  6. Duplicube：满足Harper型不等式，回答Benjamini-Zhukovskii问题

实验结果

主要结果总结

定理1（多对数度数）：d≥log^α n时，(P1)+(P2)+(P3) ⇒ ERCP

定理3（高度数）：d≥10log n/ε时，(P1)+(P2') ⇒ ERCP，其中(P2')要求|U|≤min{Cd log n, ε⁵n}时e(U,U^C)≥(1-ε³)d|U|

定理4（低度数）：d=ω(1)时，(P1)+强(P3)（|U|≤(d log n)^(5log log n)）⇒ ERCP

定理2（紧性）：存在d-正则图G满足：

  • (P1)成立
  • |U|≤log(n/d)/(40c₁)时，|N(U)|≥d|U|
  • |U|≤ε³d log(n/d)/(100c₁)时，e(U,U^C)≥(1-ε³)d|U|
  • 但whp第二大连通分量≥εd log(n/d)/(30c₁)=ω(log n)

条件的必要性分析

  • (P1)的必要性：17已证明全局扩张太弱时，巨连通分量可能是o(n)
  • (P3)的紧性：定理2证明在常数因子意义上紧
  • (P2)的必要性：开放问题（问题6.1），但定理3和4显示在某些情况下可移除

与已有结果比较

图类已有证明本文方法优势
完全图Erdős-Rényi 1960定理3统一框架
(n,d,λ)-图Frieze et al. 2004定理3/4不依赖混合引理
超立方体QdAjtai et al. 1982定理1不依赖乘积结构
随机d-正则图隐含于31定理1显式条件
Duplicube未知定理1新结果

相关工作

历史发展

  1. Erdős-Rényi (1960)：建立G(n,p)的相变理论
  2. Broadbent-Hammersley (1957)：引入渗流模型
  3. Ajtai-Komlós-Szemerédi (1982)：证明超立方体的ERCP，首次使用"处处稠密"策略
  4. Bollobás-Kohayakawa-Łuczak (1992)：超立方体的另一证明

常度数情况

  • Alon-Benjamini-Stacey (2004)：高围长扩张图有巨连通分量
  • Krivelevich-Lubetzky-Sudakov (2020)：巨连通分量阶为y(ε)n，但第二大可达|V|^a（任意a<1）
  • Diskin-Krivelevich (2025, 18)：本文姊妹篇，处理常度数情况

度数序列与随机性

  • Van der Hofstad (2023, 32)：给定度数序列时巨连通分量的普遍界
  • Lichev-Mitsche-Perarnau (2024)：度数序列随机图的阈值刻画
  • Alimohammadi-Borgs-Saberi (2023)：大集合扩张下的局部结构决定巨连通分量

本文定位

本文是第一个为度数增长的正则图提供纯扩张性质的统一充分必要条件刻画，并证明条件紧性。

结论与讨论

主要结论

  1. 对于度数增长的d-正则图，温和的全局边扩张加上对小集合（大小O(d log n)）的良好扩张控制，足以保证ERCP
  2. 小集合扩张条件在常数因子意义上是紧的
  3. 提供了统一的证明框架，不依赖特殊结构（乘积、伪随机性等）

局限性

  1. 顶点扩张(P2)的必要性未解决：问题6.1提出，是否存在满足(P1)和(P3)但不展现ERCP的图？
  2. 常数依赖性：定理中的常数C依赖于ε, c₁, c₂, c₃, α，具体依赖关系未完全优化
  3. 定量紧性：定理2给出定性紧性，但常数因子的精确匹配仍有改进空间
  4. 度数范围：d=ω(1)但d=o(log n)的情况需要定理4的强假设

未来方向

  1. 问题6.1：刻画(P2)的必要性
  2. 全局与局部扩张的定量权衡：论文指出(P1)越强则(P3)可越弱，精确刻画这种权衡
  3. 其他图类：排列面体（permutahedron）13是否可用类似框架？
  4. 算法应用：扩张条件是否可用于高效采样或近似算法？
  5. 推广到非正则图：13,15,30显示不规则图可能不展现ERCP，但能否给出更精细的条件？

深度评价

优点

  1. 理论深度：
    • 提供了统一的数学框架，避免了特例分析
    • 紧性结果（定理2）证明条件几乎最优
    • 技术创新（处处稠密性、递归路径构造）具有独立价值
  2. 证明技术：
    • 双曝光技术的精妙应用（p₂=ε³/d的选择与泰勒展开相关）
    • 间隙引理的常数精确控制
    • 概率估计的细致处理（如引理3.1的森林计数）
  3. 应用广泛性：
    • 恢复多个经典结果（完全图、超立方体、伪随机图）
    • 解决开放问题（duplicube的ERCP）
    • 为随机d-正则图提供显式条件
  4. 写作清晰度：
    • 结构清晰：背景→主要结果→证明→紧性→应用
    • 技术路线明确：四步证明策略易于理解
    • 符号系统完善

不足

  1. 条件复杂性：
    • 三个性质(P1)(P2)(P3)的相互作用不够直观
    • 常数c₁, c₂, c₃, C之间的依赖关系未明确给出
    • 实际验证图是否满足条件可能困难
  2. 开放问题：
    • (P2)的必要性未解决，理论图景不完整
    • 定理2的构造虽证明紧性，但常数匹配不精确
  3. 技术局限：
    • 对d=ω(1)但d=o(log n)需要定理4的强假设（集合大小到(d log n)^(5log log n)）
    • 证明技术高度依赖正则性假设，推广到非正则图困难
  4. 应用指导：
    • 对于给定图，如何高效验证(P2)(P3)？
    • 缺少算法或计算方面的讨论

影响力

  1. 对领域的贡献：
    • 为渗流理论提供了新的统一视角
    • 可能启发其他随机图模型的研究
    • 姊妹篇18扩展到常度数，形成完整理论
  2. 实用价值：
    • 为网络鲁棒性分析提供理论基础
    • 可用于设计具有良好渗流性质的网络拓扑
    • 扩张性质在计算机科学中有广泛应用
  3. 可复现性：
    • 纯理论证明，完全可复现
    • 证明技术详尽，关键引理都有完整证明
    • 定理2的构造可实际实现

适用场景

  1. 理论研究：
    • 随机图理论
    • 渗流理论
    • 图扩张性质研究
    • 相变现象的普适性类研究
  2. 网络科学：
    • 网络鲁棒性分析（节点/边失效）
    • 传染病传播模型（渗流对应传播）
    • 社交网络连通性分析
  3. 组合优化：
    • 图划分问题
    • 扩张图构造
    • 随机算法设计

参考文献（关键文献）

  1. 20 Erdős-Rényi (1960): 随机图相变的奠基性工作
  2. 1 Ajtai-Komlós-Szemerédi (1982): 超立方体渗流，首次使用"处处稠密"
  3. 22 Frieze-Krivelevich-Martin (2004): 伪随机图的ERCP
  4. 29 Krivelevich-Lubetzky-Sudakov (2020): 常度数高围长扩张图
  5. 32 Van der Hofstad (2023): 巨连通分量的普遍界
  6. 17 Diskin et al. (2024): 作者之前关于等周不等式与渗流的工作
  7. 18 Diskin-Krivelevich (2025): 本文姊妹篇（常度数情况）

总体评价：这是一篇高质量的理论数学论文，为渗流理论提供了深刻的统一框架。技术上严谨创新，结果具有广泛适用性，紧性分析完善了理论图景。主要遗憾是(P2)的必要性未完全解决，但这也为后续研究留下了有价值的方向。该工作对组合数学和概率论领域具有重要影响，并与网络科学有潜在联系。