Hello,
$G(n,m)$ is the family of all graphs with $n$ vertices and $m$ edges (I consider $m < n$). Each graph in $G(n,m)$ is selected with uniform probability. What is the probability that the graph selected has exactly $c$ connected components?
An equivalent question is: what is the probability that exactly $k$ edges should be removed from the selected graph in order to make it a forest (graph without cycles)?
There is a solution for the case of $k = 0$ here.
Thank you.
That depends on what $m$ and $k$ are. If $m$ is of order $Cn$ then the number of components is roughly Gaussian with mean and variance of order $n$. This should give the correct probability for $k$ reasonably close to the median. It should be possible to compute the rate function if $k$ is much larger or smaller.
If $m$ is larger, the Gaussian behaviour persists with different normalization until $m\approx n\log n$. At that scale, the number of components becomes Poisson. This persists up to much higher $n$, though once $m>n\log n$ the graph is connected with high probability.
If you are interested in a particular regime of $m,k$, I or others could probably give more details or references.
