How many labelled disconnected simple graphs have n vertices and floor((n choose 2)/2) edges? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T19:17:27Z http://mathoverflow.net/feeds/question/13088 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13088/how-many-labelled-disconnected-simple-graphs-have-n-vertices-and-floorn-choose How many labelled disconnected simple graphs have n vertices and floor((n choose 2)/2) edges? Richard Stanley 2010-01-27T01:24:11Z 2010-01-27T05:54:54Z <p>I would like to know the asymptotic number of labelled disconnected (simple) graphs with n vertices and $\lfloor \frac 12{n\choose 2}\rfloor$ edges.</p> http://mathoverflow.net/questions/13088/how-many-labelled-disconnected-simple-graphs-have-n-vertices-and-floorn-choose/13104#13104 Answer by Douglas Zare for How many labelled disconnected simple graphs have n vertices and floor((n choose 2)/2) edges? Douglas Zare 2010-01-27T05:54:54Z 2010-01-27T05:54:54Z <p>The vast majority of disconnected graphs have a single isolated vertex.</p> <p>Let $A$ be a nonempty proper subset of $\{1,...,n\}$ of size $a$. Let $s(a)$ be the number of graphs with $e=\lfloor \frac12 {n \choose 2}\rfloor$ edges which have no edges from $A$ to $A^c$.</p> <p>We want to count the union of all of these. Inclusion-exclusion works, with the dominant terms coming from when $a=1$.</p> <p>An upper bound is the sum of $s(a)$ over all $A$ of size at most $n/2$, which is at most $n ~s(1)$ + ${n\choose 2}s(1)$ + $2^ns(3)$.</p> <p>To get a lower bound, subtract the number of graphs with no edges connecting $A$ to $A^c$ or edges connecting $B$ to $B^c$ for all disjoint $\{A,B\}$. Denote this by $s(\#A,\#B)$. So, subtract </p> <p>${n\choose2}s(1,1) + 3^ns(1,2)$ from $n~s(1)$. </p> <p>The rest should be routine estimates on $s(1)$, $s(2)$, $s(3)$, $s(1,1)$, and $s(1,2)$.</p> <p>$s(a,b) \le s(a+b)$.</p> <p>$s(a) = ({n\choose 2} -a(n-a))$ choose $e$. </p> <p>Let the total number of graphs with $e$ edges be $\#G = s(0)$.</p> <p>$$s(a)/\#G = \prod_{i=0}^{a(n-a)-1} \frac{\lceil{n\choose2}/2\rceil-i}{{n\choose2}-i}$$.</p> <p>$s(2)/s(1) \le 2^{-n+3}$.</p> <p>$s(3)/s(1) \le 2^{-2n+8}$.</p> <p>The dominant term in both the upper bound and the lower bound is $n~s(1)$.</p> <p>If I calculated correctly, that's asymptotic to $\frac 2 e n 2^{-n} ~\#G$.</p>