8
$\begingroup$

Is there an way to estimate (if not calculate) the number of possible non-isomorphic graphs of 50 vertices and 150 edges?

$\endgroup$
2
  • 3
    $\begingroup$ Yes (answer soon). $\endgroup$ Dec 6, 2015 at 0:15
  • 3
    $\begingroup$ what makes that question a research question? I don't see what is special about the values 50 and 150 and the answers are also just numbers; does that help anyone? $\endgroup$ Dec 6, 2015 at 15:21

1 Answer 1

9
$\begingroup$

The simplest guess one could make is $\frac{1}{50!} { {50 \choose 2} \choose 150}$. That is, we first count the number of labeled such graphs, then assume that most of them have trivial automorphism group so we can approximately divide out by $50!$ when removing the labels. You can estimate how big this is using Stirling's formula.

Edit: Actually, you can also just ask WolframAlpha to compute this estimate. You get $7.028... \times 10^{131}$, which is apparently within 1% of the true answer according to Brendan McKay.

$\endgroup$
13
  • 11
    $\begingroup$ Estimate $7\times 10^{131}$. An average degree of 6 is not enough to ensure asymptotically that all automorphisms are trivial, but in this case it is true for over 99% of the graphs. I have a Maple program that can get the exact number, but it ran out of memory. The same program worked in version 9.5 on a computer with 1/4 the memory. Bloat is everywhere. $\endgroup$ Dec 6, 2015 at 2:13
  • 5
    $\begingroup$ If you want an even more accurate estimate you could try sampling a few million of these graphs randomly, using nauty to compute their symmetries, and applying the Polya enumeration formula. $\endgroup$ Dec 6, 2015 at 5:02
  • 10
    $\begingroup$ That's how I got the 99%. Meanwhile, here is the exact answer: 708142715793532802254978664541059073304415243612497478993671318826722214752650148113161530130602853820921572607524821134602151577093 $\endgroup$ Dec 6, 2015 at 10:02
  • 5
    $\begingroup$ @Brendan_McKay, I dare say that if that is an exact answer to the question in the title, it surely deserves to be expanded to an actual answer, with an explanation :-) $\endgroup$ Dec 6, 2015 at 19:59
  • 2
    $\begingroup$ @Gerhard the estimate is lower, because here we count an isomorphism class weighted by $1/|G|$ instead of $1$, where $G$ is its automorphism group. Think about the case where we want to count all graphs with two vertices and one edge: the estimate suggests $1/2!$, the correct answer is $1$. $\endgroup$ Dec 8, 2015 at 17:09

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.