随机图中的集团数量

Question

有一个随机图$ g（n，p）$带有$ n $ nodes（由于吉尔伯特）。每个可能的边缘都将独立插入$ g（n，p）$，并带有概率$ p $。令$ x_k $为$ g（n，p）$中的$ k $的集团数量。

我知道$ mathbb {e}（x_k）= tbinom {n} {k} {k} cdot p^{ tbinom {k} {2}}} $，但是我如何证明它？

如何证明$ mathbb {e}（x _ { log_2n}） ge1 $ for $ n to to infty $？以及如何证明$ mathbb {e}（x_ {c cdot log_2n}） to $ n to to infty $和固定的，任意的常数$ c> 1 $？

Answer 1

因此，基本上涉及三个问题。

---

我知道$ e（x_k）= tbinom {n} {k} cdot p^{ tbinom {k} {2}}} $，但是我如何证明它？

您使用期望的线性和一些智能重写。首先，请注意，$$ x_k = sum_ {t subseteq v，，，| t | = k} mathbb {1} [t text {is clique}]。 $ x_k $，一个人可以简单地抽出总和（由于线性）并获得$$ mathrm {e}（x_k）= sum_ {t subseteq v， ，，| t | = k} mathrm {e} （ Mathbb {1} [t text {is clique}]）= sum_ {抽出总和，我们消除了节点子集之间的所有可能依赖性。因此，$ t $是一个集团的可能性是多少？好吧，无论$ t $由什么组成，所有边缘概率都是相等的。因此，$ mathrm {pr} [t text {is clique}] = p^{k select 2} $，因为必须存在此子图中的所有边缘。然后，总和不再取决于$ t $，使我们享受$ mathrm {e}（x_k）= p^{k select 2} sum_ {t subseteq v， ，| t | = k} 1 = {n 选择k} cdot p^{k select 2} $。

---

如何显示$ n rightarrow infty $：$ e（x _ { log_2n}） ge1 $

我不确定这是否正确。应用 边界 在二项式系数上，我们获得

$$ e（x _ { log n}）= {n select log n} cdot p^{ log n select 2} leq left（ frac {nep^ frac {（ log n） } {4}}} { log n} right）^{ log n} = left（ frac {ne cdot n^{（ log p） / 4}}} { log n}} { log n} right）^ { log n}。$$（请注意，我大致上限$ p^ frac {-1 + log n} {2} $ by $ p^ frac { frac { log n} {4} {4} $。）但是，现在可以选择$ p = 0.001 $，并获得该$ log_2 0.001 约-9.96 $，这使整个学期都达到$ 0 $的$ n $。您可能是否错过了$ P $的一些假设？