# Expected number of independent sets of size $k$ in random graph $G(n,p)$

I am looking for a formula for determining the expected number of independent sets of size $k$ (for arbitrary $k$) in a random graph $G(n,p)$. Here $n$ is the number of vertices and each edge is included with independent probability $p$. I would like to be able to calculate this for arbitrary $p$ if possible.

I have come across the article [1] which provides a formula for the special case $p = 0.5$.

I have also come across the article [2] which in p. 12 provides a value for some cases other than $p = 0.5$, so I would assume it is known for some $p$ values other than $0.5$.

My questions are:

1. Do you know how one shows, or could you provide a reference for the formula shown in [1] for the case $p = 0.5$. The paper gives some references but they are about clique problems and I am not sure how I could arrive from them to the result shown in that paper.
2. Is there a known formula for arbitrary $p$? If not, for what $p$ values is a formula known and where could I find such formulas?

• Most likely you won't find derivation of this formula in a research article, because it is a simple exercise in basic probability theory. I suggest you learn linearity of expectation and indicator random variables, then derive the formula yourself. – Denis Pankratov Jan 25 '16 at 16:44

The probability that a specific set of size $k$ is independent is exactly $(1-p)^{\binom{k}{2}}$ (why?). Linearity of expectation shows that the expected number of independent sets of size $k$ is $\binom{n}{k} (1-p)^{\binom{k}{2}}$ (why?).

This is an old thread, but I thought it was worth adding: there actually is at least one paper that derives this result (or to be precise, the equivalent result of the expected number of cliques of size $k$; cliques in $G(n,p)$ correspond to independent sets in $G(n,1-p)$). It is a conference paper, "On the Complete Subgraphs of a Random Graph" by David Matula, from 1970, available here, on the author's website. It's not a hard result to derive, but someone thought it was worth publishing at least once!

• Matula proves quite a bit more, but he does seem to consider it not completely trivial. – Yuval Filmus Feb 25 '17 at 0:28