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

$\displaystyle{ ({\color{red}\star})\qquad }$ \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} }

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

# 一阶矩方法

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

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

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

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

$\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} }$

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

$\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) }$

# 二阶矩方法

$\displaystyle{ \Pr(X\ge 1)\ge 1-o(1) }$

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

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

$\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] }$

\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} }

\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} }

\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} }