random · G(n,p) · 阈函数

随机图：概率方法与阈值现象

把一张图掷骰子掷出来：固定 n 个顶点，对每一对可能的边，独立地以概率 p 决定它出现与否——这就是 Erdős–Rényi 模型 G(n,p)。随着 p 由 0 升到 1，图从一盘散沙长成完全图。引人入胜之处在于：几乎所有「单调性质」（连通、含三角形、无孤立点……）并非平滑出现，而是在某个 阈函数 (threshold) 附近从「几乎必不发生」骤变到「几乎必然发生」。下面拖动 p，亲历两道关口—— $p \approx 1/n$ 处巨型分支 (giant component) 涌现， $p \approx \ln n / n$ 处图达到连通。

模型定义： G(n,p) 是 n 个标号顶点上的随机图，其 C(n,2) 条可能的边各自独立地以概率 p 出现。期望边数为 $p\cdot C(n,2)$ ，每个顶点的度服从二项分布 $Bin(n-1, p)$ ，平均度 $\approx p(n-1)$ 。下面的演示给每条可能的边预先分配一个固定阈值 $u_e \in [0,1)$ （用可复现的 LCG 生成），约定「 $p \ge u_e$ 时该边出现」——于是拖大 p 只会单调加边，同一颗种子下完全可复现，便于观察性质如何随 p 接连点亮。

巨型分支 (giant component) 在 $p \approx 1/n$ 涌现。 令平均度 $c = p(n-1) \approx pn$ 。当 c < 1 时，所有连通分支都很小（最大分支约 $O(\log n)$ 个顶点）；当 c > 1 时，会突然出现一个含正比例顶点的唯一巨型分支。这是 Erdős–Rényi 的相变结论，临界点正是 c = 1，即 $p \approx 1/n$ 。把 p 调到 1/n 两侧来回拨，观察「最大分支占比」如何从接近 0 跃起。

连通性阈值是 $p \approx \ln n / n$ 。 更精确地，取 p = (ln n + c) / n：当 $c \to -\infty$ 时 G(n,p) 几乎必然不连通，当 $c \to +\infty$ 时几乎必然连通；在 c 取定值时，无孤立点的概率趋于 e^{−e^{−c}}。连通的最后障碍恰是孤立点：一旦没有孤立点，通常整图也就连通了——所以「无孤立点」与「连通」共享同一道阈值 ln n / n。轴上青色刻度即此关口。

概率方法 (probabilistic method): 要证明「存在一张具备性质 P 的图」，不必动手构造——只需证明随机图以正概率具备 P，则这样的图必定存在。Erdős 用它给出 Ramsey 数下界：在 K_N 的边上各自独立地抛硬币染红 / 蓝，一个固定的 k 顶点集合单色的概率是 2^{1−C(k,2)}；若 C(N,k)·2^{1−C(k,2)} < 1，则期望的单色 k-团个数小于 1，故存在一种染色不含任何单色 k-团，即 R(k,k) > N。由此得下界 R(k,k) > 2^{k/2}（略去常数），这是一个纯粹由「正概率」推出存在性、却不指明具体染色的经典论证。