526互联

Erdős–Rényi 随机图的连通性

发布时间 2023-04-26 10:59:36作者: EntropyIncreaser

对于给定的 \(n\) 个顶点, 对于任意一个点对, 以 \(p\) 的概率连边, 这样得到的一个无向简单图上的概率分布, 称为 Erdős–Rényi 随机图模型.

那么, \(p\) 有多大的时候, 得到的图将会有很大概率连通呢? Erdős 和 Rényi 给出了如下结果:

对于 \(p = (\log n + c) / n\), 记事件 \(A(G)\) 为 "\(G\) 是连通图", 那么

\[\lim_{n\to\infty} \Pr[A(G_{n,p})] = e^{-e^{-c}}. \]

这在随机图的研究中一般称为一个阈值结果 (threshold result), 如果 \(p=o(\log n / n)\), 那么图几乎一定不是连通的 (概率趋于 \(0\)), 而如果 \(p = \omega(\log n / n)\), 那么图几乎一定是连通的!

令人意外的是, 证明这个结果的思路其实相当直接, 或者说, 证明它的途径是基于这样一个直觉:
对于 \(p=(\log n + c)/n\) 的随机图, 当 \(c\) 变大的时候, 基本上图已经是一个连通了所有点的连通块, 剩下的功夫只是通过提升概率将剩余的孤立点加到连通块中.

一个图不连通, 当且仅当它没有大小 \(\leq n/2\) 的连通块. 我们记事件 \(A_k\) 是 "\(G_{n, p}\) 里存在大小为 \(k\) 的连通块", 那么根据 union bound, 就有

\[\Pr[A_1] \leq \Pr[A(G_{n,p})] \leq \sum_{k=1}^{n/2} \Pr[A_k]. \]

我们接下来要分别控制 \(\Pr[A_1]\) 和 \(\sum_{k=2}^{n/2} \Pr[A_k]\).

控制 \(\sum_{k=2}^{n/2} \Pr[A_k]\)

这一部分通过一阶矩方法 (也即 Markov 不等式) 就能够得到我们需要的结果.

对于一个大小为 \(k\) 的连通块, 它至少有一颗生成树. 所以我们可以用大小为 \(k\) 的支撑子树的数量来控制存在大小为 \(k\) 的连通块的概率:

\[\Pr[A_k] \leq \binom{n}{k} k^{k-2} p^{k-1}(1-p)^{k(n-k)}. \]

首先 \(\binom{n}{k}\) 是选这个连通块占据的位置, \(k^{k-2}\) 是 Cayley 公式, 也即 \(k\) 个点的完全图的生成树的数量, 我们只要求所选的这 \(k-1\) 条边是存在的, 并且这个集合和外部集合之间的边都是不存在的, 分别对应于 \(p^{k-1},(1-p)^{k(n-k)}\).

对于小的 \(k\) 和更大的 \(k\) 我们分别控制, 对于 \(k< 10\), 我们分别证明每一项是 \(o(1)\) 就可以了, 有:

\[\begin{align*} &\quad \binom{n}{k} k^{k-2} p^{k-1}(1-p)^{k(n-k)}\\ &\sim Cn^k p^{k-1} (1-p)^{-nk}\\ &\sim Cn^k p^{k-1} \exp \{ -nkp \}\\ &= C n^k p^{k-1} \exp \{ -k(\log n + c_n) \}\\ &\sim Cp^{k-1} \\ &= O\left(\left(\frac{\log n}{n}\right)^k\right). \end{align*}\]

对于 \(10 \leq k\leq n/2\), 我们用到的不等式有:

  • \(\binom n k \leq n^k / k!\).
  • \(\frac 1{k!} \leq (\frac{e}{k})^k\), 这可以通过对 \(\frac 1{k!} \leq \sum_{j\geq 0} \frac{x^{j-k}}{j!} = x^{-k}e^x\) 带入 \(x=k\) 得到.
  • \(n-k \geq n/2\).
  • \(1-p \leq e^{-p}\).

都加进去, 我们得到了

\[\begin{align*} &\leq \left(\frac{ne}{k}\right)^k k^{k-2} p^{k-1} \exp \left\{-\frac{nkp}2 \right\} \\ &= \frac 1{k^2p} \left( e n p \exp \left\{ -\frac{np}2 \right\}\right)^k \\ &\leq \frac 1 p \left(\frac{e(\log n + c)}{n^{1/2}}\right)^k, \end{align*}\]

那么由于 \(\frac{e(\log n + c)}{n^{1/2}}\to 0\), 我们有

\[\begin{align*} &\quad \sum_{k=2}^{n/2} \Pr[A_k]\\ &\leq O\left(\frac{\log n} n\right) + \frac 1 p\sum_{k=10}^{n/2}\left(\frac{e(\log n + c)}{n^{1/2}}\right)^k\\ &= O\left(\frac{\log n} n\right) + (1+o(1))\frac{1}{p} \cdot \left(\frac{e(\log n + c)}{n^{1/2}}\right)^{10}\\ &= O\left(\frac{\log n} n\right) +(1+o(1)) n^{-4} \cdot O \left((\log n)^9\right)\\ &= O\left(\frac{\log n} n\right). \end{align*} \]

控制 \(\Pr[A_1]\)

注意到, 图中的某一个点是孤立点的概率是 \((1 - p)^{n-1} \sim e^{-np} = e^{-c}/n\), 所以期望的孤立点数量应该趋近于 \(\lambda = e^{-c}\). 如果假装 \(n\) 个点的概率是独立的, 那么孤立点的数量 \(X\) 的分布应该收敛到 Poisson 分布 \(\Pr[X = k] = e^{-\lambda} \frac{\lambda^k}{k!}\). 当然实际上这是不独立的, 但由于每个点之间的关联很小, 这个结论仍然是成立的, 我们有标准的技术来处理这个问题.

首先让我们来计算任意阶矩 \(\mathbb E[\binom X k]\), 这相当于是任选 \(k\) 个点看看它们是不是孤立点, 因此有

\[\begin{align*} \mathbb E \left[\binom X k\right] &= \binom n k (1-p)^{\binom k 2 + k(n-k)}\\ &\sim \frac{n^k}{k!} (1-p)^{nk}\\ &\sim \frac{n^k}{k!} \exp \{ -nkp \}\\ &= \frac{e^{-ck}}{k!}\\ &= \frac{\lambda^k}{k!}. \end{align*}\]

我们小学就学过了容斥原理 \(\Pr[X=0] = \mathbb E[\binom X 0]-\mathbb E[\binom X 1]+\mathbb E[\binom X 2] - \cdots\), 看起来如果能逐项取极限就和我们想要的结论一致了, 当然实际上我们还得稍微克制一下.

考虑求和

\[\sum_{j=0}^k (-1)^j \binom X j = (-1)^k\binom{X-1}{k}, \]

当 \(X=0\) 时右式总是 \(1\), 否则有 \(\binom{X-1}{k} \geq 0\), 所以

\[ \begin{align*} \sum_{j=0}^{2k} (-1)^j \mathbb E \left[ \binom X j \right] &\geq \Pr[X = 0], \\ \sum_{j=0}^{2k+1} (-1)^j \mathbb E \left[ \binom X j \right] &\leq \Pr[X = 0]. \end{align*} \]

这也就是称作所谓的 Bonferroni 不等式.

那么如果固定了 \(k\), 我们对两边取极限, 就有

\[ \begin{align*} \sum_{j=0}^{2k} (-1)^j \frac{\lambda^j}{j!} &\geq \limsup_{n\to \infty} \Pr[X = 0], \\ \sum_{j=0}^{2k+1} (-1)^j \frac{\lambda^j}{j!} &\leq \liminf_{n\to \infty} \Pr[X = 0] . \end{align*} \]

因此再对 \(k\) 取极限, 我们就有

\[\lim_{n\to \infty} \Pr[X = 0] = \sum_{j=0}^\infty (-1)^j \frac{\lambda^j}{j!} = e^{-\lambda}. \]

这也就得到了

\[\Pr[A(G_{n,p})] \to e^{-e^{-c}}. \]

上面的容斥手法在 The Probabilistic Method 一书中称为 Brun 筛法. 更一般地, 它还可以进一步得到 \(\Pr[X=k] \to e^{-\lambda} \lambda^k/k!\), 也就是说 \(X\) 确实趋近于 Poisson 分布. 所以更精细地说, 我们有如下结果:

\(G_{n,p}\) 趋近于有 \(e^{-e^{-c}-ck}/k!\) 的概率形如 "\(k\) 个孤立点, 剩下的点连通".

更一般地说, 对于满足一定条件的随机变量 \(X\), 我们只要确定了任意阶矩 \(\mathbb E[X_n^k] \to \mathbb E[X^k]\), 就能够得到分布的收敛性. 有些时候这是比控制特征函数要容易的.