Is there an way to estimate (if not calculate) the number of possible non-isomorphic graphs of 50 vertices and 150 edges?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ Yes (answer soon). $\endgroup$– Brendan McKayCommented 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$– Manfred WeisCommented Dec 6, 2015 at 15:21
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
13
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.
answered Dec 6, 2015 at 1:56
-
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$ Commented 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$ Commented Dec 6, 2015 at 5:02
-
10$\begingroup$ That's how I got the 99%. Meanwhile, here is the exact answer: 708142715793532802254978664541059073304415243612497478993671318826722214752650148113161530130602853820921572607524821134602151577093 $\endgroup$ Commented 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$ Commented 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$ Commented Dec 8, 2015 at 17:09