Expected number of m-cliques in a random graph Let $Z_m$ be a random variable that corresponds to the number of $m$-cliques in a random graph with n vertices and the probability of any edge happening is 1/2. Prove that $$ \mbox{E}[Z_m] = {n \choose m} 2^{-{m \choose 2}}.$$ 
 A: What is an $m-$clique?

 An $m$-clique is a set of $m$ vertices such that every two distinct vertices are adjacent.   IE: There is an edge connecting ever pair of vertices in the set.

How many $m$-cliques could there be?

 The number of plausible $m$-cliques in a random graph of $n$ vertices, is the count of selections for $m$ from $n$ vertices.

What is the probability that a particular $m$-clique happens.

 The probability that a particular set of $m$ vertices actually form an $m$-clique is the probability that every edge joining any two of those points are connected.  How many such edges are there ? What is the probability that all these connections happen?

Put it together using the Linearity of Expectation.

 You can do it, if you try.

A: I know this is an old problem, but I also faced the same doubt. Luckily, I was able to solve this doubt by myself. Hence, I provide how I solved it, so in case that anyone else is having the same doubt will find an easy to follow step-by-step proof of this result.
First of all, we need to understand that a clique of size $m$ is a set of m nodes, in which every node is connected to every other node (in a social network it would mean that everyone knows everyone else).
Hence in a network with $n$ nodes we choose all the subsets of size $m$. The total number of possible combinations (subsets) will be $\binom{n}{m}$.
Now we can define $\binom{n}{m}$ $X_j$ indicator r.v.s, i.e. $(X_1, X_2,...,X_\binom{n}{m}$), which indicate wheter the j subset is a clique or not.
Hence the Expected Number of cliques of size m will be the sum of those indicator r.v.s:
$E(X_1 + X_2 + ... + X_\binom{n}{m}) = E\left (\sum_{1}^{\binom{n}{m}} X_j \right )$
By symmetry of expectations we know that all those expectations are exactly the same. Hence, for example, we can multiply the Expectation of $X_1$ by $\binom{n}{m}$.
$E(X_1 + X_2 + ... + X_\binom{n}{m}) = E\left (\sum_{1}^{\binom{n}{m}} X_j \right ) = \binom{n}{m}E(X_1)$
Now by the fundamental bridge, we know that the expectation of an indicator r.v. is the same as its probability, i.e. $E(X_1) = P(X_1 = 1)$. In other words, we want to calculate the probability that the first subset of size m is a clique of size m. 
To calculate this probability we only need to know the probability  of any edge happening, which we will call $p$ (in this case it is $1/2$). Furthermore, we know that in order to form a clique all the nodes in this subset must be connected, that means that all possible combinations of 2 nodes from the $m$ subset, that is $\binom{m}{2}$. Hence:
$P(X_1 = 1) =  (p)^\binom{m}{2}  = (\frac{1}{2})^\binom{m}{2} = \frac{1}{2^\binom{m}{2}} = E(X_1)$ 
Putting all of this together, we obtain that:
$E(X_1 + X_2 + ... + X_\binom{n}{m}) = E\left (\sum_{1}^{\binom{n}{m}} X_j \right ) = \binom{n}{m}E(X_1) = \binom{n}{m}P(X_1 = 1) = \binom{n}{m} \frac{1}{2^\binom{m}{2}}$
So:
$E[Z_m]=\binom{n}{m} 2^{-\binom{m}{2}}$
where $Z_m = X_1 + X_2 + ... + X_\binom{n}{m}$
Hope this helps.
