Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
This feels like the sort of thing that would be in Harary and Palmer's Graphical Enumeration. –  Michael Lugo Jan 27 '10 at 3:02
Also, I changed the title; I almost didn't read this question because the original title was too vague. –  Michael Lugo Jan 27 '10 at 3:23
It looks like the vast majority of them have one disconnected vertex. –  Douglas Zare Jan 27 '10 at 3:58
add comment

1 Answer

The vast majority of disconnected graphs have a single isolated vertex.

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$.

We want to count the union of all of these. Inclusion-exclusion works, with the dominant terms coming from when $a=1$.

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)$.

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

${n\choose2}s(1,1) + 3^ns(1,2)$ from $n~s(1)$.

The rest should be routine estimates on $s(1)$, $s(2)$, $s(3)$, $s(1,1)$, and $s(1,2)$.

$s(a,b) \le s(a+b)$.

$s(a) = ({n\choose 2} -a(n-a))$ choose $e$.

Let the total number of graphs with $e$ edges be $\\#G = s(0)$.

$$s(a)/\\#G = \prod_{i=0}^{a(n-a)-1} \frac{\lceil{n\choose2}/2\rceil-i}{{n\choose2}-i}$$.

$s(2)/s(1) \le 2^{-n+3}$.

$s(3)/s(1) \le 2^{-2n+8}$.

The dominant term in both the upper bound and the lower bound is $n~s(1)$.

If I calculated correctly, that's asymptotic to $\frac 2 e n 2^{-n} ~\\#G$.

share|improve this answer
Thanks, this is helpful. It is related to the topological properties of random simplicial complexes. –  Richard Stanley Jan 28 '10 at 16:32
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.