most recent 30 from http://mathoverflow.net 2013-05-26T00:51:45Z http://mathoverflow.net/feeds/question/95849 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/95849/number-of-connected-components-in-a-graph-from-gn-m Marina 2012-05-03T11:45:49Z 2012-05-07T07:02:58Z

<p>Hello,</p> <p>$G(n,m)$ is the family of all graphs with $n$ vertices and $m$ edges (I consider $m &lt; 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?</p> <p>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)?</p> <p>There is a solution for the case of $k = 0$ <a href="http://mathoverflow.net/questions/57062/probability-that-a-graph-g-does-not-contain-a-cycle" rel="nofollow">here</a>.</p> <p>Thank you.</p>

http://mathoverflow.net/questions/95849/number-of-connected-components-in-a-graph-from-gn-m/96188#96188 Omer 2012-05-07T07:02:58Z 2012-05-07T07:02:58Z

<p>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.</p> <p>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.</p> <p>If you are interested in a particular regime of $m,k$, I or others could probably give more details or references.</p>