Tuesday, 18 May 2010

asymptotics - How many labelled disconnected simple graphs have n vertices and floor((n choose 2)/2) edges?

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)$ + ${nchoose 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



${nchoose2}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) = ({nchoose 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{nchoose2}/2rceil-i}{{nchoose2}-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$.

No comments:

Post a Comment