Number of connected components in a graph from G(n,m) - MathOverflow 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 Number of connected components in a graph from G(n,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 Answer by Omer for Number of connected components in a graph from G(n,m) 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>