2
$\begingroup$

Are there any non-trivial lower bounds on the number of isomorphism classes for a graph with $N$ vertices?

For example there are at least $N(N-1)/2$ isomorphism classes (counting one for the number of possible edges in our graph) but as $N$ increases, there will clearly be a lot more.

$\endgroup$
1
$\begingroup$

You really need to say what you mean by non-trivial. What do you want to use the bound for? But, gripes aside, $2^{\binom{n}2}/n!$ is a lower bound and asymptotically tight.

$\endgroup$
  • $\begingroup$ I meant $N(N-1)/2$ as the trivial lower bound. Do you have a reference for this? $\endgroup$ – rwolst Oct 28 '14 at 19:04
  • $\begingroup$ The number of graphs in the isomorphism class of $G$ is $n!/|\mathrm{Aut}(G)|$, so it's at most $n!$. So the number of isomorphism classes is at least $2^n/n!$. I do not think a reference is necessary. $\endgroup$ – Chris Godsil Oct 28 '14 at 20:20
  • $\begingroup$ $2^{{n \choose 2}}/n!$. Yes that is enough. $\endgroup$ – rwolst Oct 28 '14 at 22:05

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.