这里所说的二阶矩(Second Moment)其实可以理解成在上一篇笔记 中的中所说的的方差,期望是一阶矩，而方差就是二阶矩。本篇笔记中的中模型大多数都是利用二阶矩来进行证明的，最常用的工具就是Chebyshev不等式。

随机图(Random Graphs)

一个随机图是按照如下规则生成的一个图结构:

1. 图中一共有n个节点,即|V|=n
2. 图中任意两个定点之间以p的概率出现边，且这些边之间是相互独立的。

这样生成一个随机图的过程就是随机图模型，用G(n,p)来表示。在随机图模型上有很多有趣的性质，接下来我们将分别讨论。

图的单调属性(Monotone Properties)

定义:图属性

令Gn=2(n2)表示所有具有n个点的图所能够生成的所有图结构的集合,图的属性是一个布尔函数P:Gn→{0,1},且这个函数并不依赖的于顶点的顺序。也即是说，如果G和H是同构的，则P(G)=P(H)

定义: 图的单调属性

图的单调属性是指，假设G,H都是有n个顶点的图,且满足G⊆H, 如果G有属性P则H必有属性P

图的单调属性有很多，比如:

• 是否存在汉米尔顿路径
• 是否含有和H同构的子图

当然也有属性不是单调的，比如:

• 是否存在欧拉路径

图的单调属性和单调函数的概念很相似，可以做一些类比。

对于所有图的单调属性，有如下的定理:

定理:

令P是一个图的单调属性,假设G1=G(n,p1),G2=G(n,p2),且0≤p1≤p2≤1，则

Pr[P(G1)]≤Pr[P(G2)]

证明:

要证明这个定理，需要用到一个称为coupling的技巧，所谓coupling是指，要是使得两个问题发生耦合，用某种方法将两个不同的问题捆绑到一起，这样比较利于分析。

在我们这个具体的证明中，假设p1,p2是共享一个随机源的，这强迫使它们发生了联系。对于任意的(u,v)∈V来说，令Xu,v表示一个[0,1]上的分布。

当且仅当Xuv∈[0,p1]时，(u,v)∈G1;当且仅当Xuv∈[0,p2]时，(u,v)∈G2,又因为p1≤p2，所以(u,v)∈G1⇒(u,v)∈G2,也即G1⊆G2.

根据图的单调性的定义，如果P(G1)=1，则P(G2)=1,也就说说Pr[P(G1)]≤Pr[P(G2)]

◻

阈值现象(Threshold Phenomenon)

在随机图上有着一个比较好玩的性质,称为阈值现象(Threshold Phenomenon).它描述的是随机图(G(n,p))上的某一些属性是随着p激增的，当p小于某个阈值p(n)时，随机图几乎没有对应的属性P;而当p大于某个阈值p(n)时，随机图G(n,p)则会有很高的概率有对应的属性P。用数学语言来描述是:

• 当n≪p(n)时, 随着n→∞,Pr[P(G(n,p))]=0
• 当n≫p(n)时, 随着n→∞,Pr[P(G(n,p))]=1

4-clique

在图中，4-clique是指如下的子图(子图中有4个顶点，且两两有边):

定理:

一个随机图含有4-clique的阈值是n−23

证明:

令S表示随机图G(n,p)中的任意一个由4个顶点组成的子图，XS为一个二值变量:

则Pr[XS=1]=p6,因为4-clique一共有6条边，而每条出现的概率是p.

X表示G(n,p)中4-clique的个数，也即X=∑S∈(n4)XS.

根据阈值现象的定义，我们只需要证明如下两个引理:

1. 当p=o(n−23)时，随着n→∞,Pr[X≥1]→0
2. 当p=w(n−23)时，随着n→∞,Pr[X≥1]→1

首先，我们来证明第一个:

根据Markov不等式，我们有:

又因为p=o(n−23), 所以:

即Pr[x≥1]→0

现在我们来证明第二个引理,首先Pr[x≥1]→1我们可以看成证明Pr[X=0]→0¹,这两者是等价的。 则:

其中，E[X]=(n4)p6=O(n4p6)

剩下的我们就需要计算Var[X],根据方差的性质:

现在我们需要分别计算Var[XS]和Cov(XS,XT)

所以∑S∈(n4)Var[XS]=n4p6

接下来我们要计算Cov(XS,XT),此时需要分情况讨论:

• |S∩T|≤1时，S,T没有公共边，因此Cov(S,T)=0
• |S∩T|=2时，S,T有一条公共边，且一共有11条边，因此

又因为|S∪T|=6,因此在这种情况下，∑S,T∈(n4),S≠TCov(XS,XT)=O(n6p11)

• |S∩T|=3时,S,T有3条公共边，且一共有9条边，因此:

又因为|S∪T|=5,因此在这种情况下，∑S,T∈(n4),S≠TCov(XS,XT)=O(n5p9)

综合上述所有情况,Var[X]=O(n4p6+n6p11+n5p9)

所以:

因此，当n=w(n−23)时,Pr[X=0]→0

◻

Share on: Twitter ❄ Facebook ❄ Email

---

---