13
$\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$?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
10
$\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$?

Improve this answer
$\endgroup$
4
  • $\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
    Commented May 28, 2012 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
    Commented May 28, 2012 at 20:47
  • $\begingroup$ What is with the third question? $\endgroup$
    – Queue
    Commented May 28, 2012 at 22:45
  • $\begingroup$ It suffers the same problem as the second question. Sorry, I should have clarified that. $\endgroup$
    – HdM
    Commented May 28, 2012 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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