概率论与数理统计 (Spring 2023)/Threshold of k-clique in random graph

在 Erdős-Rényi 随机图模型 [math]\displaystyle{ G(n,p) }[/math] 中，一个随机无向图 [math]\displaystyle{ G }[/math] 以如下的方式生成：图 [math]\displaystyle{ G }[/math] 包含 [math]\displaystyle{ n }[/math] 个顶点，每一对顶点之间都独立同地以概率 [math]\displaystyle{ p }[/math] 连一条无向边。如此生成的随机图记为 [math]\displaystyle{ G\sim G(n,p) }[/math]。

固定整数 [math]\displaystyle{ k\ge 3 }[/math]，考虑随机图 [math]\displaystyle{ G\sim G(n,p) }[/math] 包含 [math]\displaystyle{ K_k }[/math]（[math]\displaystyle{ k }[/math]-团，[math]\displaystyle{ k }[/math]-clique）子图概率。

特别地，对于任意固定（即，常数）的整数 [math]\displaystyle{ k\ge 3 }[/math]，我们将证明存在函数 [math]\displaystyle{ p_k(n) }[/math] 使得对所有足够大的 [math]\displaystyle{ n }[/math] 和随机图 [math]\displaystyle{ G\sim G(n,p) }[/math] 有

[math]\displaystyle{ ({\color{red}\star})\qquad }[/math] [math]\displaystyle{ \begin{align} \Pr\left(G\text{ 包含子图 }K_k\right) =\begin{cases} o(1) & \text{如果} p=o(p_k(n))\\ 1-o(1) & \text{如果} p=\omega(p_k(n)) \end{cases} \end{align} }[/math]

这描述了“包含 [math]\displaystyle{ k }[/math]-团“这一性质，在随机图 [math]\displaystyle{ G(n,p) }[/math] 上，展现出的一种所谓的阈值现象：随着参数 [math]\displaystyle{ p }[/math] 从远小于 [math]\displaystyle{ p_k(n) }[/math] 增长到远大于 [math]\displaystyle{ p_k(n) }[/math]，“包含 [math]\displaystyle{ k }[/math]-团“这一事件在随机图 [math]\displaystyle{ G(n,p) }[/math] 上从渐进几乎从不（asymptotically almost never）发生变为渐进几乎一定（a.a.s.）发生。

固定整数 [math]\displaystyle{ k\ge 3 }[/math]，假设[math]\displaystyle{ k=O(1) }[/math]为常数。抽取随机图 [math]\displaystyle{ G\sim G(n,p) }[/math]。令随机变量 [math]\displaystyle{ X }[/math] 表示 [math]\displaystyle{ G }[/math] 中包含的 [math]\displaystyle{ k }[/math]-团的个数，因此有：

[math]\displaystyle{ \Pr\left(G\text{ 包含子图 }K_k\right) = \Pr(X\ge 1) }[/math].

一阶矩方法

根据马尔可夫不等式：

[math]\displaystyle{ \Pr(X\ge 1)\le\mathbb{E}[X] }[/math].

因此，通过计算 [math]\displaystyle{ X }[/math] 的期望（一阶矩），可得到概率 [math]\displaystyle{ \Pr\left(G\text{ 包含子图 }K_k\right) }[/math] 的上界。

对于顶点集合 [math]\displaystyle{ [n] }[/math] 的任意 [math]\displaystyle{ k }[/math]-子集 [math]\displaystyle{ S\in{[n]\choose k} }[/math]，定义指示随机变量 [math]\displaystyle{ I_S=I(K_S\subseteq G) }[/math]，即 [math]\displaystyle{ I_S=1 }[/math] 当且仅当点集 [math]\displaystyle{ S }[/math] 在随机图 [math]\displaystyle{ G }[/math] 中构成了一个 [math]\displaystyle{ k }[/math]-团。根据这个定义，有：

• [math]\displaystyle{ X=\sum_{S\in{[n]\choose k}}I_S }[/math]
• [math]\displaystyle{ \mathbb{E}[I_S]=\Pr(K_S\subseteq G)=p^{{k\choose 2}} }[/math]

于是根据期望的线性：

[math]\displaystyle{ \mathbb{E}[X]=\sum_{S\in{[n]\choose k}}\mathbb{E}[I_S]={n\choose k}p^{{k\choose 2}} }[/math].

对于常数 [math]\displaystyle{ k=O(1) }[/math]，当 [math]\displaystyle{ n }[/math] 足够大时，[math]\displaystyle{ {n\choose k}p^{{k\choose 2}}=\Theta\left(n^kp^{k(k-1)/2}\right) }[/math]。这提示我们将函数 [math]\displaystyle{ p_k(n) }[/math] 做如下定义：

[math]\displaystyle{ p_k(n)=n^{-2/(k-1)} }[/math].

于是，容易验证有：

[math]\displaystyle{ \mathbb{E}[X]=\Theta\left(n^kp^{k(k-1)/2}\right)=\begin{cases} o(1) & \text{如果 } p=o(p_k(n))=o\left(n^{-2/(k-1)}\right)\\ \omega(1) & \text{如果 } p=\omega(p_k(n))=\omega\left(n^{-2/(k-1)}\right) \end{cases} }[/math]

特别地，当 [math]\displaystyle{ p=o(p_k(n))=o\left(n^{-2/(k-1)}\right) }[/math] 时，[math]\displaystyle{ \mathbb{E}[X]=o(1) }[/math]。根据马尔可夫不等式：

[math]\displaystyle{ \Pr\left(G\text{ 包含子图 }K_k\right)=\Pr(X\ge 1)\le \mathbb{E}[X]=o(1). }[/math]

因此，[math]\displaystyle{ ({\color{red}\star}) }[/math] 中的概率上界已得到证明。

事实上，这一结果可以更加直接地使用 union bound 证明：

[math]\displaystyle{ \Pr\left(G\text{ 包含子图 }K_k\right)=\mbox{$\Pr\left(\bigcup_{S\in{[n]\choose k}}(K_S\subseteq G)\right)$}\le {n\choose k}p^{{k\choose 2}}=o(1)\qquad\left(\text{如果 $p=o(p_k(n))$}\right) }[/math]

尽管如此，对于一阶矩的分析，有助于我们猜测出正确的阈值 [math]\displaystyle{ p_k(n) }[/math]，而且对于更高阶矩的估计也是必要的。

二阶矩方法

为了完全证明 [math]\displaystyle{ ({\color{red}\star}) }[/math]，我们需要补全其中的概率下界，即在 [math]\displaystyle{ \mathbb{E}[X]=\omega(1) }[/math] 的情况下，证明

[math]\displaystyle{ \Pr(X\ge 1)\ge 1-o(1) }[/math]

很遗憾，为实现这一目的，仅知道 [math]\displaystyle{ \mathbb{E}[X]=\omega(1) }[/math] 是不够的。我们还需要知道关于随机变量 [math]\displaystyle{ X }[/math] 更多的信息，比方说它的方差（二阶中心矩）。

根据切比雪夫不等式：

[math]\displaystyle{ \Pr(X=0)\le \Pr(|X-\mathbb{E}[X]|\ge \mathbb{E}[X])\le \frac{\mathbf{Var}[X]}{\mathbb{E}[X]^2} }[/math]

于是，上述目标归结为证明方差和期望之间有如下渐进关系： [math]\displaystyle{ \mathbf{Var}[X]=o\left(\mathbb{E}[X]^2\right) }[/math]。实际上我们证明了更强的性质

[math]\displaystyle{ \mathbb{E}[X^2]=o\left(\mathbb{E}[X]^2\right) }[/math].

这足以推出 [math]\displaystyle{ \mathbf{Var}[X]=\mathbb{E}[X^2]-\mathbb{E}[X]^2\le \mathbb{E}[X^2]=o\left(\mathbb{E}[X]^2\right) }[/math]。

还记得 [math]\displaystyle{ X=\sum_{S\in{[n]\choose k}}I_S }[/math]，于是有：

[math]\displaystyle{ \mathbb{E}\left[X^2\right] = \mathbb{E}\left[\left(\sum_{S\in{[n]\choose k}}I_S\right)^2\right] = \sum_{S\in{[n]\choose k}}\mathbb{E}[I_S^2] + \sum_{\substack{S,T\in{[n]\choose k}\\S\neq T}}\mathbb{E}[I_SI_T] }[/math]

我们将分别计算这两项。首先，由于随机变量 [math]\displaystyle{ I_S }[/math] 取值为0或1，因此 [math]\displaystyle{ I_S^2=I_S }[/math]，于是有：

[math]\displaystyle{ \begin{align} \sum_{S\in{[n]\choose k}}\mathbb{E}[I_S^2] = \sum_{S\in{[n]\choose k}}\mathbb{E}[I_S] = \mathbb{E}[X] \end{align} }[/math]

另一方面，[math]\displaystyle{ I_SI_T=1 }[/math] 当且仅当 [math]\displaystyle{ S }[/math] 和 [math]\displaystyle{ T }[/math] 在随机图 [math]\displaystyle{ G }[/math] 中都是 [math]\displaystyle{ k }[/math]-团，于是：

[math]\displaystyle{ \begin{align} \sum_{\substack{S,T\in{[n]\choose k}\\S\neq T}}\mathbb{E}[I_SI_T] &= \sum_{\substack{S,T\in{[n]\choose k}\\S\neq T}}\Pr((K_S\cup K_T)\subseteq G)\\ &= \sum_{\ell=0}^{k-1}\sum_{|S\cap T|=\ell}p^{2{k\choose 2}-{\ell\choose 2}}\\ &\le \sum_{\ell=0}^{k-1}{n\choose 2k-\ell} {2k-\ell\choose k}{k\choose \ell} p^{2{k\choose 2}-{\ell\choose 2}} && \left(\text{因为 }{2k-\ell\choose k}{k\choose \ell}\le 2^{2k}=O(1)\right)\\ &= O\left(n^{2k}p^{2{k\choose 2}}\cdot\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right)\\ &= \mathbb{E}[X]^2\cdot O\left(\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right). && \left(\text{因为 }\mathbb{E}[X]=\Theta\left(n^kp^{{k\choose 2}}\right)\right) \end{align} }[/math]

综上，我们有 [math]\displaystyle{ \mathbf{Var}[X]\le \mathbb{E}[X^2]\le \mathbb{E}[X]+\mathbb{E}[X]^2\cdot O\left(\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right) }[/math]，于是：

[math]\displaystyle{ \begin{align} \frac{\mathbf{Var}[X]}{\mathbb{E}[X]^2} &\le \frac{\mathbb{E}[X^2]}{\mathbb{E}[X]^2}\\ &\le \frac{1}{\mathbb{E}[X]} + O\left(\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right)\\ &= O\left(\sum_{\ell=2}^{k}n^{-\ell}p^{-{\ell\choose 2}} \right) && \left(\text{因为 }\mathbb{E}[X]=\Theta\left(n^kp^{{k\choose 2}}\right)\right)\\ &=o(1). && (\text{当 }p=\omega(p_k(n))) \end{align} }[/math]

正如我们之前分析的，根据切比雪夫不等式，这证明了当 [math]\displaystyle{ p=\omega(p_k(n))=\omega\left(n^{-2/(k-1)}\right) }[/math] 时，有 [math]\displaystyle{ \Pr(X=0)=o(1) }[/math]。和一阶矩方法的部分合起来，这证明了 [math]\displaystyle{ ({\color{red}\star}) }[/math]。