3
$\begingroup$

A rather tight lower bound $c(n)$ of the number of unlabeled digraphs of order $n$ (loops allowed) seems to be

$$c(n) = 2^{n^2}/n!$$

because there are $2^{n^2}$ labeled graphs, almost all of them are asymmetric, thus division by $n!$ is almost always "correct", but yields a slightly too small result, because it is sometimes not correct. How can this error be estimated, of which order is it? But most of all I'd like to know:

Is the growth rate of $c(n)$ super- or supra-exponential?

I know Stirling's formula, but I didn't manage to simplify the resulting expression.

$\endgroup$
3
$\begingroup$

If you apply Stirling's formula,

$c(n)\approx \frac{2^{n^2}e^{-n}}{n^n}$.

$\log c(n)\approx n^2 \log 2 - n \log n + n$

As the log increases faster than $n$, the growth is faster than any exponential.

$\endgroup$
2
$\begingroup$

See the OEIS, sequence A000088 for an asymptotic formula for the error. In particular, if $G(n)$ is the number of unlabeled graphs on n nodes, then

$$ {G(n) \over c(n)} = 1 + {n^2 - n \over 2^{n-1}} + O(n^2 2^{-2n}) $$

as $n \to \infty$. I suspect there is a simple combinatorial explanation for that first term but I don't know what it is; the source is Harary and Palmer, Graphical Enumeration, which may explain that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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