CS2304关于随机图的内容。

Introduction

G(n, p) Model [Erd ሷ𝑜s and R ƴ𝑒nyi1960]:

|V|=n is the number of vertices, and for and different $u ,v \in V$,$Pr({u, v} \in E)=p$

G实际上表示一个概率空间

• 𝑮(𝑛, 1/2)

$$\mu=n \mu'=E(K)=\frac{n}{2},$$ $$\sigma^{2}=n\left(\sigma'\right)^{2}=Var(K)=n / 4$$

(CLT) Near the mean, the binomial distribution is well approximated by the normal distribution.

$$\frac{1}{\sigma \sqrt{2 \pi}} e^{-\frac{(k-n \mu)^{2}}{2 \sigma^{2}}}=\frac{1}{\sqrt{\pi n / 2}} e^{-\frac{(k-n / 2)^{2}}{n / 2}}$$

Lemma.

• For all integers n , k with n ≥ k ≥ 2; the probability that $G \in G(n, p)$ has a set of k independent vertices is at most

  $$Pr(\alpha(G) \geq k) \leq\left(\begin{array}{l}n \\ k\end{array}\right)(1-p)^{\left(\begin{array}{l}k \\ 2\end{array}\right)}$$

• the probability that $G \in G(n, p)$ has a set of k clique is at most

$$Pr(\omega(G) \geq k) \leq\left(\begin{array}{l}n \\ k\end{array}\right)(p)^{\left(\begin{array}{l}k \\ 2\end{array}\right)}$$

• The expected number of k -cycles in $G \in G(n, p)$ is $E(x)=\frac{(n)_{k}}{2 k} p^{k}$ .

Properties of Almost All Graphs

• 定义：当 时，若图性质 在 中出现的概率：

  • 趋近于 1：称性质对几乎所有图成立
  • 趋近于 0：称性质对几乎所有图不成立

• 关键定理：

  1. 诱导子图存在性：
     对任意常数 和任意图 ，几乎所有 包含 的诱导副本。

     $$\Pr[\text{不存在诱导 } H] \leq (1 - r)^{\lfloor n/k \rfloor} \xrightarrow{n \to \infty} 0$$

  2. 邻接性质 ：
     对任意不相交顶点集 （），存在顶点 满足：

     • 与 中所有顶点相邻
     • 与 中所有顶点不相邻 $$\Pr[\exists U,W \text{ 无合适 } v] \leq n^{i+j} (1 - p^iq^j)^{n-i-j} \xrightarrow{n \to \infty} 0$$

染色数（Chromatic Number）

• 定义：

  • 顶点染色：映射 满足相邻顶点颜色不同
  • 染色数 ：最小的

• 下界估计：对任意 ，几乎所有图满足：

  $$\chi(G) > \frac{\log(1/q)}{2+\epsilon} \cdot \frac{n}{\log n}$$

  证明：利用独立集上界：

  $$\Pr(\alpha(G) \geq k) \leq \binom{n}{k} q^{\binom{k}{2}} \leq n^k q^{k(k-1)/2}$$

  取 时概率趋近于 0。

相变（Phase Transition）

• 阈值定义：存在函数 使得：

  • 当 时， 几乎必然不满足性质
  • 当 时， 几乎必然满足性质

• 相变表：
  | 概率 | 图结构性质 |
  |—————————————-|————————————————————————|
  | | 树组成的森林，无大于 的连通分量 |
  | | 所有连通分量大小为 | | | 连通分量大小为 | | | 存在巨连通分量 + 的小分量 |
  | | 直径为 2 |
  | | 巨连通分量 + 孤立顶点 |
  | | 孤立顶点消失；出现 Hamilton 回路；直径 |
  | | 存在大小为 的团 |

矩方法（Moment Methods）

一阶矩法

• Markov 不等式：对非负随机变量 和 ： $$\Pr(X \geq a) \leq \frac{E[X]}{a}$$
• 应用： $$\Pr(X > 0) \leq E[X]$$ 若 ，则性质几乎必然不发生。

二阶矩法

• 定理：若 且 ，则 几乎必然成立：

  $$\Pr(X = 0) \leq \Pr(|X - E[X]| \geq E[X]) \leq \frac{\text{Var}(X)}{E^2[X]} \to 0$$

• 应用示例（直径 2 的阈值）：

  • 阈值点：
  • 定义指示变量： $$I_{ij} = \begin{cases} 1 & \{i,j\} \notin E \text{ 且无公共邻居} \\ 0 & \text{否则} \end{cases}$$
  • 当 ：
    • ： → 直径
    • ： → 直径

单调性质与阈值存在性

• 单调性质：添加边不会破坏该性质（如连通性、无孤立点）
• 定理：每个单调性质 存在阈值 ，其中 是满足下式的最小实数： $$\Pr(G(n, p(n)) \text{ 满足 } Q) = \frac{1}{2}$$
• 证明关键：
  • 当 ：-重复制技术证明
  • 当 ：