15
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This feels like the sort of thing that would be in Harary and Palmer's Graphical Enumeration. $\endgroup$ Jan 27, 2010 at 3:02
  • $\begingroup$ Also, I changed the title; I almost didn't read this question because the original title was too vague. $\endgroup$ Jan 27, 2010 at 3:23
  • $\begingroup$ It looks like the vast majority of them have one disconnected vertex. $\endgroup$ Jan 27, 2010 at 3:58

1 Answer 1

11
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks, this is helpful. It is related to the topological properties of random simplicial complexes. $\endgroup$ Jan 28, 2010 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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