2026-08-07 · 最后一个孤点消失时

0. 导读与元结构 (Orientation & Meta-structure)

起点问题。 给定 $n$ 个标号顶点，把每一条可能的边都以概率 $p$ 独立加入。随着 $p$ 增大，图何时从碎片变成连通整体？“平均度大约为多少”只给出尺度猜测；真正的问题带有两层量词：先固定一列概率 $p=p(n)$，再令 $n\to \mathrm{\infty }$，研究连通事件的概率是否趋于 $0$、$1$，或某个非退化极限。

对象层。 对每个整数 $n\ge 1$ 与 $p\in [0,1]$，Erdős–Rényi binomial random graph（二项随机图）$G(n,p)$ 是顶点集 $[n]=\{1,\dots ,n\}$ 上的随机简单图；对每条 $e\in (\genfrac{}{}{0ex}{}{[n]}{2})$，指标变量

$$I_e={\mathbf{1}}_{\{e\in E(G)\}}$$

相互独立，且 $\mathbb{P}(I_e=1)=p$。样本空间因此是 $\{0,1{\}}^{(\genfrac{}{}{0ex}{}{n}{2})}$ 上的乘积概率空间。

性质与量词层。 图性质 $\mathcal{A}=({\mathcal{A}}_n{)}_{n\ge 1}$ 是各阶标号图集合的一列。若加边不会破坏 $\mathcal{A}$，称其为 increasing property（递增性质）；连通性就是递增性质。对事件列 $A_n$，

$$\mathbb{P}(A_n)\to 1$$

称 $A_n$ asymptotically almost surely（渐近几乎必然，a.a.s.）发生。函数 $p_{\ast }(n)>0$ 是 $\mathcal{A}$ 的一个 threshold function（阈值函数），若对每列 $p=p(n)$ 都有

$$\frac{p(n)}{p_{\ast }(n)}\to 0⟹\mathbb{P}(G(n,p)\in \mathcal{A})\to 0,$$

以及

$$\frac{p(n)}{p_{\ast }(n)}\to \mathrm{\infty }⟹\mathbb{P}(G(n,p)\in \mathcal{A})\to 1.$$

今天不只定位连通阈值 $p_{\ast }(n)=\log n/n$，还进入更细的 additive critical window（加性临界窗）

$$p=\frac{\log n+c}{n},c\in \mathbb{R},$$

在其中连通概率不会塌缩为 $0$ 或 $1$。

前置、机制与去向。 前置知识只有有限图、指示变量、期望与方差、Markov/Chebyshev 不等式、Poisson 分布。主导 proof engines 是：

1. 先数局部障碍——孤立点；
2. 用 factorial moments（阶乘矩）识别 Poisson 极限；
3. 用 union bound（一致并合界）排除大小 $2$ 到 $n/2$ 的其他分量；
4. 由“无孤点”升级到“连通”。

这是三日 anchor micro-arc 的第 1 日。今日处理较晚的连通转变；下一日回到更稀疏的 $p\asymp 1/n$，研究 giant component（巨分量）的诞生；第三日再用 Chernoff/大偏差语言统一阈值证明中的指数代价与组合熵。

1. 核心概念、定理与谱系 (Concept, Theorem & Lineage)

1.1 为什么先看孤立点

设 $X_0=X_0(G)$ 为 $G(n,p)$ 的孤立点数：

$$X_0:=\sum _{v=1}^n{\mathbf{1}}_{\{\mathrm{deg}(v)=0\}}.$$

一个固定顶点 $v$ 孤立，当且仅当与它相接的 $n-1$ 条边都缺失，因此

$$\mathbb{P}(v\text{ 孤立})=(1-p{)}^{n-1},\mathbb{E}{X}_0=n(1-p{)}^{n-1}.$$

若 $p=(\log n+c)/n$，则 $p\to 0$ 且

$$(n-1)\log (1-p)=-(n-1)p+O(n{p}^2)=-\log n-c+o(1),$$

因为 $n{p}^2=O((\log n{)}^2/n)\to 0$。故

$$\boxed{{\displaystyle \mathbb{E}{X}_0⟶e^{-c}.}}$$

这解释了尺度：当 $np$ 约为 $\log n$ 时，单个顶点孤立的概率约为 $e^{-np}\approx 1/n$，乘上 $n$ 个候选点后，障碍数仍是常数量级。

但期望不是分布。$\mathbb{E}{X}_0\to e^{-c}$ 并不能单独推出“存在孤点”的概率，更不能推出连通概率；下一步必须处理顶点孤立事件之间的依赖。

1.2 阶乘矩把依赖压缩为 Poisson 极限

对非负整数值随机变量 $X$ 与整数 $r\ge 1$，定义 falling factorial（下降阶乘）

$$(X{)}_r=X(X-1)\cdots (X-r+1).$$

固定 $r$ 个互异顶点全都孤立，需要删去所有至少有一个端点落在该 $r$ 点集中的边。这样的边数是

$$r(n-r)+(\genfrac{}{}{0ex}{}{r}{2})=r(n-1)-(\genfrac{}{}{0ex}{}{r}{2}).$$

于是，对每个固定整数 $r\ge 1$，

$$\begin{array}{rl}\mathbb{E}(X_0{)}_r& =(n{)}_r(1-p{)}^{r(n-1)-(\genfrac{}{}{0ex}{}{r}{2})}\\ & =n^r(1+o(1))\exp (-prn+o(1))\\ & ⟶e^{-cr}.\end{array}$$

而 $Z\sim \mathrm{Poisson}(\lambda )$ 满足

$$\mathbb{E}(Z{)}_r={\lambda }^r.$$

Poisson 分布由其阶乘矩刻画，故 factorial-moment method（阶乘矩法）给出

$$\boxed{{\displaystyle X_0\stackrel{d}{\to }\mathrm{Poisson}(e^{-c}).}}$$

特别地，

$$\mathbb{P}(X_0=0)⟶\mathbb{P}(\mathrm{Poisson}(e^{-c})=0)=e^{-e^{-c}}.$$

这还只是“无孤立点”的概率。若要得到连通性，必须证明临界窗中其他不连通方式都可忽略。

1.3 排除大小至少为二的分离分量

记 $C_k$ 为大小恰为 $k$ 的连通分量数。图不连通，当且仅当存在某个 $1\le k\le n/2$ 使 $C_k\ge 1$。对 $2\le k\le n/2$，固定一个 $k$ 元顶点集 $S$。若 $S$ 是一个连通分量，则：

1. $S$ 与补集之间的 $k(n-k)$ 条边全部缺失；
2. 诱导子图 $G[S]$ 连通，因而包含某棵 spanning tree（生成树）。

Cayley 公式给出 $S$ 上共有 $k^{k-2}$ 棵标号树。对每棵树，要求其 $k-1$ 条边出现；忽略 $S$ 内其他边只会给上界。因此

$$\mathbb{E}{C}_k\le (\genfrac{}{}{0ex}{}{n}{k})k^{k-2}{p}^{k-1}(1-p{)}^{k(n-k)}.$$

在 $p=(\log n+c)/n$ 下，把 $2\le k\le n/2$ 分成小 $k$ 与大 $k$ 两段，分别使用

$$(\genfrac{}{}{0ex}{}{n}{k})\le {\left(\frac{en}{k}\right)}^k,1-p\le e^{-p},$$

可得

$$\sum _{k=2}^{\lfloor n/2\rfloor }\mathbb{E}{C}_k=o(1).$$

这里的核心竞争是：选择 $S$ 带来组合熵 $(\genfrac{}{}{0ex}{}{n}{k})$，禁止跨割边带来概率惩罚 $e^{-pk(n-k)}$；在连通临界窗中，后者足以压过所有 $k\ge 2$ 的分离分量，而 $k=1$ 的孤立点恰好仍保留常数强度。[2][3]

由 Markov 不等式，

$$\mathbb{P}(\sum _{k=2}^{\lfloor n/2\rfloor }{C}_k>0)=o(1).$$

因此

$$0\le \mathbb{P}(X_0=0)-\mathbb{P}(G(n,p)\text{ 连通})\le \mathbb{P}(\sum _{k=2}^{\lfloor n/2\rfloor }{C}_k>0)=o(1).$$

1.4 主定理与谱系

定理（Erdős–Rényi 连通临界窗）。 设 $c\in \mathbb{R}$ 固定，并对每个 $n$ 令

$$p_n=\frac{\log n+c}{n}.$$

若 $G_n\sim G(n,p_n)$，则

$$X_0(G_n)\stackrel{d}{\to }\mathrm{Poisson}(e^{-c}),$$

且

$$\boxed{{\displaystyle \mathbb{P}(G_n\text{ 连通})⟶e^{-e^{-c}}.}}$$

更粗地，若 $\omega (n)\to \mathrm{\infty }$，则

$$p=\frac{\log n-\omega (n)}{n}⟹G(n,p)\text{ a.a.s. 不连通},$$

而

$$p=\frac{\log n+\omega (n)}{n}⟹G(n,p)\text{ a.a.s. 连通}.$$

历史谱系。 Erdős 与 Rényi 在 1959 年开始系统研究随机图，1960 年的 On the Evolution of Random Graphs 明确提出随边数增加研究“典型结构”与 threshold functions（阈值函数）；他们在引言中记录了连通性的尖锐临界尺度，并把问题置于随机图“演化”的统一框架中。[1] 现代 $G(n,p)$ 表述把独立边模型与 Poisson 逼近、耦合方法结合起来，使证明机制更透明。[2][3]

Graduate / modern extension：hitting time。 给每条可能边独立赋一个均匀时间戳，并依时间先后加入，得到随机图过程

$$G_0\subset G_1\subset \cdots \subset G_{(\genfrac{}{}{0ex}{}{n}{2})}.$$

对递增性质 $\mathcal{A}$ 定义

$$\tau (\mathcal{A}):=min\{m:G_m\in \mathcal{A}\}.$$

显然

$$\tau (\delta \ge 1)\le \tau (\text{connected}),$$

因为连通图必无孤点。更强的 hitting-time theorem（击中时刻定理）说

$$\boxed{{\displaystyle \mathbb{P}(\tau (\delta \ge 1)=\tau (\text{connected}))\to 1.}}$$

它不是定点极限的机械改写：必须在同一个随机过程上同时控制整个临界时间窗。其内容是——以高概率，最后一个孤立点被接入的那一刻，恰是整张图首次连通的时刻。[3]

2. 固定模板习题 (Template Exercise)

题目

设 $X_n\sim \mathrm{Bin}(n,p_n)$，其中

$$p_n\to 0,n{p}_n\to \lambda \in (0,\mathrm{\infty }).$$

证明：对每个固定整数 $k\ge 0$，

$$\mathbb{P}(X_n=k)⟶e^{-\lambda }\frac{{\lambda }^k}{k!}.$$

并说明为什么这是一类“许多候选、单次极稀有、总强度有限”问题的标准 Poisson approximation（Poisson 逼近）模板。

模板识别

看到三件事就应想到 Poisson 极限：试验次数 $n\to \mathrm{\infty }$；单次成功概率 $p_n\to 0$；平均成功数 $n{p}_n$ 收敛到有限正数。目标不是中心极限定理的 $\sqrt{n}$ 波动，而是固定 $k$ 的概率质量。

分级提示

1. 从二项分布的精确公式
   $$\mathbb{P}(X_n=k)=(\genfrac{}{}{0ex}{}{n}{k})p_n^k(1-p_n{)}^{n-k}$$
   开始，把三部分分开处理。
2. 对固定 $k$，证明
   $$(\genfrac{}{}{0ex}{}{n}{k})p_n^k=\frac{(n{)}_k}{k!}{p}_n^k⟶\frac{{\lambda }^k}{k!}.$$
3. 用 $\log (1-p_n)=-p_n+O(p_n^2)$，并由 $n{p}_n^2=(n{p}_n)p_n\to 0$，处理 $(1-p_n{)}^n$。
4. 最后说明 $(1-p_n{)}^{-k}\to 1$，再把三项相乘。

3. 大家之言 (Mathematician in Their Own Words)

人物与文本。 Terence Tao 在个人研究博客 What's new 的文章 A partial digestion of the HRT counterexample（2026-08-06）中，尝试高层次拆解一个推翻 Heil--Ramanathan--Topiwala conjecture 的新构造。该结果使用了 AI 辅助的策略发现和传统数值计算；Tao 关注的不是“用了 AI”这一标签本身，而是候选结果如何进入可接受的数学记录。[4]

核验短引。

“However, I think the authors have disclosed their AI use responsibly, with the final arguments written by hand with a readable overview of the argument, as well as proper discussion of methods, relation to past literature, and other independent numerical checks on the result.”

中译。 “不过，我认为作者负责任地披露了 AI 的使用：最终论证由人工写成，附有可读的论证总览，并恰当地讨论了方法、与既有文献的关系，以及对结果所作的其他独立数值核验。”

评注。 这段话给出一种可执行的数学验收标准：generation（生成）与 acceptance（接受）必须分离。一个系统可以帮助发现样本空间、数值参数或证明路线，但进入数学知识的仍应是可读论证、明确的文献位置和独立核验。它也照见今天的阈值证明：数值实验可以提示 $\log n/n$，期望计算可以提示孤立点障碍；真正封口的却是阶乘矩、分量并合界与清楚的量词。随机性或 AI 都可以参与发现，不可替代验收。

4. 反例与边界 (Counterexample & Boundary)

4.1 “没有孤立点”并不蕴含“连通”

取 $n\ge 4$，令

$$G=K_2\bigsqcup K_{n-2}.$$

逐项检查：

1. $G$ 是 $n$ 个顶点上的有限简单图；
2. $K_2$ 中两个顶点的度都是 $1$；
3. $K_{n-2}$ 中每个顶点的度都是 $n-3\ge 1$；
4. 因而 $\delta (G)\ge 1$，即没有孤立点；
5. 两个完全图之间没有边，所以 $G$ 有两个连通分量，故不连通。

因此，确定性命题

$$\delta (G)\ge 1⟹G\text{ 连通}$$

是假的。Section 1 的正确结论是依赖模型和尺度的渐近陈述：当 $G\sim G(n,(\log n+c)/n)$ 时，除孤立点外的其他分离分量以概率 $o(1)$ 消失；在随机图过程中，对所有临界时刻的联合控制又给出 hitting-time 等式。不能删掉“$G(n,p)$”“临界窗”或“以高概率”。

4.2 为什么“期望趋于无穷”仍不够

再看稍低的边界尺度

$$p=\frac{\log n-\log \log n}{n}.$$

此时

$$\mathbb{E}{X}_0=n(1-p{)}^{n-1}\sim \log n\to \mathrm{\infty }.$$

但一般而言，$\mathbb{E}{X}_n\to \mathrm{\infty }$ 并不推出 $\mathbb{P}(X_n>0)\to 1$：很大的期望可能由极罕见而极大的取值造成。这里之所以能推出存在孤点，是因为还可计算二阶矩。对不同顶点 $u\ne v$，二者同时孤立需要缺失 $2n-3$ 条边，故

$$\mathbb{E}(X_0{)}_2=n(n-1)(1-p{)}^{2n-3}.$$

于是

$$\frac{\mathbb{E}(X_0{)}_2}{(\mathbb{E}{X}_0{)}^2}=\frac{n-1}{n(1-p)}⟶1.$$

从而

$$\frac{\mathrm{Var}(X_0)}{(\mathbb{E}{X}_0{)}^2}=\frac{1}{\mathbb{E}{X}_0}+\frac{\mathbb{E}(X_0{)}_2}{(\mathbb{E}{X}_0{)}^2}-1⟶0.$$

Chebyshev 不等式遂给出 $X_0/\mathbb{E}{X}_0\to 1$ in probability（依概率收敛），特别是 $\mathbb{P}(X_0=0)\to 0$。边界在此暴露：first moment（第一矩）定位候选尺度，dependence control（依赖控制）才把尺度变成概率结论。

5. 今日一问与数学地图 (Question & Map)

今日一问。 在同一组独立均匀边时间戳构成的随机图过程中，定点结论

$$\mathbb{P}(G(n,p)\text{ 连通})-\mathbb{P}(X_0(G(n,p))=0)\to 0$$

为什么还不足以直接推出

$$\mathbb{P}(\tau (\delta \ge 1)=\tau (\text{connected}))\to 1?$$

你会怎样把整个临界窗离散化，并控制“某一时刻无孤点却仍有大小至少为二的分量”这一存在于时间轴上的坏事件？

方向提示。 先辨认量词差异：前者对每个给定 $p_n$ 控制一个截面，后者要控制一个随机时间区间内“存在某时刻”。逐点 $o(1)$ 误差不能未经 uniformity（统一性）就对许多时刻并合。可尝试先夹住最后孤点消失的时间，再利用过程的单调耦合与临界窗内分量结构的统一估计。

数学地图。

$$\begin{array}{c}\text{指示变量、阶乘矩、Poisson 逼近}\\ \downarrow \\ G(n,p)\text{ 与孤立点计数}\\ \downarrow \\ p\sim {\displaystyle \frac{\log n}{n}}\text{ 的连通临界窗}\\ \swarrow \searrow \\ \text{随机图过程与 hitting time}\text{尖锐阈值与影响度}\\ \downarrow \downarrow \\ \text{Hamilton 圈、完美匹配的局部障碍}\text{Friedgut--Kalai 阈值理论}\end{array}$$

另有一条必须区分的更早路线：

$$p\asymp \frac{1}{n}⟶\text{局部分枝过程}⟶\text{巨分量相变},$$

而不是连通性。巨分量在平均度常数量级时出现；彻底吞并最后的孤立点则要等到平均度约为 $\log n$。下一日将解释这两个阈值为何相差一个对数因子。

附录 A：习题完整解答 (Full Solution)

展开完整解答

可复用模板：有限强度稀有事件的 Poisson 极限。

固定整数 $k\ge 0$。由二项分布公式，

$$\mathbb{P}(X_n=k)=(\genfrac{}{}{0ex}{}{n}{k})p_n^k(1-p_n{)}^{n-k}.$$

先处理组合因子。因为 $k$ 固定，

$$(\genfrac{}{}{0ex}{}{n}{k})p_n^k=\frac{(n{)}_k}{k!}{p}_n^k=\frac{(n{p}_n{)}^k}{k!}\prod _{j=0}^{k-1}(1-\frac{j}{n})⟶\frac{{\lambda }^k}{k!}.$$

其次处理没有额外成功的概率。由 $p_n\to 0$，

$$\log (1-p_n)=-p_n+O(p_n^2).$$

又因 $n{p}_n\to \lambda$ 且 $p_n\to 0$，

$$n{p}_n^2=(n{p}_n)p_n\to 0.$$

所以

$$n\log (1-p_n)=-n{p}_n+O(n{p}_n^2)⟶-\lambda ,$$

从而

$$(1-p_n{)}^n⟶e^{-\lambda }.$$

最后，由 $k$ 固定且 $p_n\to 0$，

$$(1-p_n{)}^{-k}⟶1.$$

三者相乘即得

$$\begin{array}{rl}\mathbb{P}(X_n=k)& =\left[(\genfrac{}{}{0ex}{}{n}{k})p_n^k\right][(1-p_n{)}^n][(1-p_n{)}^{-k}]\\ & ⟶\frac{{\lambda }^k}{k!}{e}^{-\lambda }.\end{array}$$

这正是 $\mathrm{Poisson}(\lambda )$ 在 $k$ 处的概率质量。

模板为何可复用。 “$n$ 个候选 + 每个以概率 $p_n$ 稀有发生 + $n{p}_n\to \lambda$”意味着期望事件数维持有限强度。独立情形直接给二项到 Poisson；弱依赖情形常改用 factorial moments、Chen--Stein method 或 dependency graph。Section 1 的孤立点不是独立指标，但固定多个顶点同时孤立的概率仍可精确计算，所以阶乘矩模板继续有效。

资料与来源 (Sources)

1. P. Erdős and A. Rényi, “On the Evolution of Random Graphs,” Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5 (1960), 17–61. 原始论文扫描；引言给出随机图演化、典型结构与阈值函数框架，并记录连通性的尖锐临界尺度。https://www.renyi.hu/~p_erdos/1960-10.pdf
2. Alan Frieze and Michał Karoński, Introduction to Random Graphs, online book manuscript, version dated 20 February 2026，尤其 Chapter 1（models and thresholds）与 Chapter 4（connectivity）。https://www.math.cmu.edu/~af1p/BOOK.pdf
3. Oleg Pikhurko, “Thresholds for Some Basic Properties,” Eight Lectures on Random Graphs, Lecture 2, Carnegie Mellon University. 包含孤立点的阶乘矩、连通临界窗以及随机图过程的 hitting-time formulation。https://www.math.cmu.edu/~af1p/MAA2005/L2.pdf
4. Terence Tao, “A partial digestion of the HRT counterexample,” What's new, 6 August 2026. 本期引文取自 Tao 对 AI 辅助结果之披露、可读论证、文献关系与独立数值核验的评述。https://terrytao.wordpress.com/2026/08/06/a-partial-digestion-of-the-hrt-counterexample