CS2304关于随机图的内容。

1. 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$

• 𝑮(𝑛, 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)}$$