Question

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.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top