11
$\begingroup$

There is a family of random graphs $G(n, p)$ with $n$ nodes (due to Gilbert). Each possible edge is independently inserted into $G(n, p)$ with probability $p$. Let $X_k$ be the number of cliques of size $k$ in $G(n, p)$.

I know that $\mathbb{E}(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$, but how do I prove it?

How to show that $\mathbb{E}(X_{\log_2n})\ge1$ for $n\to\infty$? And how to show that $\mathbb{E}(X_{c\cdot\log_2n}) \to 0$ for $n\to\infty$ and a fixed, arbitrary constant $c>1$?

$\endgroup$
9
$\begingroup$

So basically there are three questions involved.


I know that $E(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$, but how do I prove it?

You use the linearity of expectation and some smart re-writing. First of all, note that $$ X_k = \sum_{T \subseteq V, \, |T|=k} \mathbb{1}[T \text{ is clique}].$$ Now, when taking the expectation of $X_k$, one can simply draw the sum out (due to linearity) and obtain $$ \mathrm{E}(X_k) = \sum_{T \subseteq V, \, |T|=k} \mathrm{E}(\mathbb{1}[T \text{ is clique}]) = \sum_{T \subseteq V, \, |T|=k} \mathrm{Pr}[T \text{ is clique}]$$ By drawing out the sum, we eliminated all possible dependencies between subsets of nodes. Hence, what is the probability that $T$ is a clique? Well, no matter what $T$ consists of, all edge probabilities are equal. Therefore, $\mathrm{Pr}[T \text{ is clique}] = p^{k \choose 2}$, since all edges in this subgraph must be present. And then, the inner term of the sum does not depend on $T$ anymore, leaving us with $\mathrm{E}(X_k) = p^{k \choose 2} \sum_{T \subseteq V, \, |T|=k} 1 = {n \choose k} \cdot p^{k \choose 2}$.


How to show that for $n\rightarrow\infty$: $E(X_{\log_2n})\ge1$

I am not entirely sure whether this is even correct. Applying a bound on the binomial coefficient, we obtain

$$E(X_{\log n}) = {n \choose \log n} \cdot p^{\log n \choose 2} \leq \left(\frac{n e p^\frac{(\log n)}{4}}{\log n}\right)^{\log n} = \left(\frac{ne \cdot n^{(\log p) / 4}}{\log n}\right)^{\log n}.$$ (Note that I roughly upper bounded $p^\frac{-1 + \log n}{2}$ by $p^\frac{\log n}{4}$.) However, now one could choose $p = 0.001$, and obtain that $\log_2 0.001 \approx -9.96$, which makes the whole term go to $0$ for large $n$. Are you maybe missing some assumptions on $p$?

$\endgroup$
  • $\begingroup$ Is that right? $E(X_{\log n}) = {n \choose \log n} \cdot p^{\log n \choose 2} \leq \left(\frac{n e p^\frac{(\log n)}{4}}{\log n}\right)^{\log n}$. Does it not have to be $$E(X_{\log n}) = {n \choose \log_2 n} \cdot p^{\log_2 n \choose 2} \leq \left(\frac{n e}{\log_2 n}\right)^{\log n}\cdot p^\frac{(\log_2 (n)\cdot e)^2}{4}$$ but now i dont know how to go on $\endgroup$ – user1374864 May 28 '12 at 20:25
  • $\begingroup$ I applied said bound only on ${n \choose \log n}$. For $p$, you can observe that ${\log n \choose 2} = (\log n) (\log n -1)/2$. Now since $p \leq 1$, we want to make its exponent smaller (convince yourself why). For reasonably big $n$, we have that $(\log n) (\log n -1)/2 > (\log n)^2 / 4$. Therefore the above computation should be correct... $\endgroup$ – HdM May 28 '12 at 20:47
  • $\begingroup$ What is with the third question? $\endgroup$ – Queue May 28 '12 at 22:45
  • $\begingroup$ It suffers the same problem as the second question. Sorry, I should have clarified that. $\endgroup$ – HdM May 28 '12 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.