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

From TCS Wiki
Revision as of 13:42, 18 April 2023 by Etone (talk | contribs)
Jump to navigation Jump to search

在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))\\ \omega(1) & \text{如果} p=\omega(p_k(n)) \end{cases} }[/math]

特别地,当 [math]\displaystyle{ p=o(p_k(n)) }[/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] 中的概率上界已得到证明。

二阶矩方法

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

[math]\displaystyle{ \Pr(X\ge 1)\le 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{ X=\sum_{S\in{[n]\choose k}}I_S }[/math],有:

[math]\displaystyle{ \mathbf{Var}[X] =\sum_{S\in{[n]\choose k}}\mathbf{Var}[I_S] + \sum_{\substack{S,T\in{[n]\choose k}\\S\neq T}}\mathbf{Cov}(I_S,I_T) }[/math]

我们将分别计算这两项。首先:

[math]\displaystyle{ \begin{align} \sum_{S\in{[n]\choose k}}\mathbf{Var}[I_S] = \sum_{S}\left(\mathbb{E}[I_S^2]-\mathbb{E}[I_S]^2\right) \le \sum_{S}\mathbb{E}[I_S^2] = \sum_{S}\mathbb{E}[I_S] = \mathbb{E}[X] = \Theta\left(n^kp^{k(k-1)/2}\right) \end{align} }[/math]

其次:

[math]\displaystyle{ \begin{align} \sum_{\substack{S,T\in{[n]\choose k}\\S\neq T}}\mathbf{Cov}(I_S,I_T) &= \sum_{S\neq T}\left(\mathbb{E}[I_SI_T]-\mathbb{E}[I_S]\mathbb{E}[I_T]\right)\\ &\le \sum_{S\neq T}\mathbb{E}[I_SI_T]\\ &= \sum_{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}} && \text{(因为 ${2k-\ell\choose k}{k\choose \ell}=O(1)$)}\\ &= O\left(n^{2k}p^{2{k\choose 2}}\sum_{\ell=0}^{k-1} n^{-\ell}p^{-{\ell\choose 2}}\right) \end{align} }[/math]

综上,再想起 [math]\displaystyle{ \mathbb{E}[X]=\Theta\left(n^kp^{k(k-1)/2}\right) }[/math],于是有

[math]\displaystyle{ \begin{align} \frac{\mathbf{Var}[X]}{\mathbb{E}[X]^2} &\le \frac{\sum_{S}\mathbf{Var}[I_S]}{\mathbb{E}[X]^2} + \frac{\sum_{S\neq T}\mathbf{Cov}(I_S,I_T)}{\mathbb{E}[X]^2}\\ &= O\left(n^{-k}p^{-{k\choose 2}}\right)+O\left(\sum_{\ell=2}^{k-1}n^{-\ell}p^{-{\ell\choose 2}} \right)\\ &= O\left(\sum_{\ell=2}^{k}n^{-\ell}p^{-{\ell\choose 2}} \right)\\ &=o(1) \qquad\qquad \text{当 }p=\omega(p_k(n)) \end{align} }[/math]

正如我们上述分析,根据切比雪夫不等式,这证明了当 [math]\displaystyle{ p=\omega(p_k(n)) }[/math] 时,[math]\displaystyle{ \Pr(X=0)=o(1) }[/math],从而证明了 [math]\displaystyle{ ({\color{red}\star}) }[/math]