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?

[1] Chromatic and Independence Numbers of $G_{{n}, {{1}\over{2}}}$

[1] Feo, Thomas A., Mauricio GC Resende, and Stuart H. Smith. “A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set.” Operations Research 42, no. 5 (1994): 860–78.

  • 4
    $\begingroup$ 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. $\endgroup$ – 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?).

If you can't follow this calculation, please follow Denis Pankratov's advice and look up linearity of expectation and indicator random variables.


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!

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

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.