2 ms·

>The number of graphs of size n is 2^(n choose 2). This is overcounting by many orders of magnitude. For example, there's only one graph with one edge, not (n

>The number of graphs of size n is 2^(n choose 2). This is overcounting by many orders of magnitude. For example, there's only one graph with one edge, not (n choose 2). For n = 43 you're overcounting these graphs by a factor of 903. Similarly there are only two graphs with two edges (either the two edges are connected or not), not ((n choose 2) choose 2). For n = 43 you're overcounting these graphs by a factor of ~200k. For graphs with three edges you can have (1) a triangle, (2) three edges connected end to end forming a single path, (3) three connected edges forming a star, (4) two connected edges and one single, or (5) three unconnected edges. Compared to your count of ((n choose 2) choose 3), you're overcounting by a factor of about 24 million for n=43. The total (over)count is going to be dominated by graphs with approximately (n choose 2)/2 edges, which intuitively is where I also expect the overcounting factor to peak.

btilly 6y ago
I was talking about graphs up to their representation. You are talking about graphs up to isomorphism. Recognizing that two graphs are isomorphic is a potentially tricky problem. Generating them by isomorphism class is certainly not going to be the naive approach. But suppose that we are able to do so. How much does this do for us? Well, it can help us by a factor of at most n!, because you generate isomorphic graphs by permuting the vertices. Which for 43 is around 6.04152630633738e+52. For 48 is around 1.24139155925361e+61. Those are big savings to be sure, but are still dwarfed by the size of the search space. So the next thing to do is to not only try to look at each graph up to isomorphism once, but to somehow generate them in an order that makes it likely that you find cliques or independent sets early. Thereby letting you prune out big chunks of the search space. With the ability to start different computers out in different ranges so we can parallelize the search. But by now we're well down on the path to something that is very much not a naive search.

btilly 6y ago

I was talking about graphs up to their representation. You are talking about graphs up to isomorphism. Recognizing that two graphs are isomorphic is a potentially tricky problem. Generating them by isomorphism class is certainly not going to be the naive approach. But suppose that we are able to do so. How much does this do for us? Well, it can help us by a factor of at most n!, because you generate isomorphic graphs by permuting the vertices. Which for 43 is around 6.04152630633738e+52. For 48 is around 1.24139155925361e+61. Those are big savings to be sure, but are still dwarfed by the size of the search space. So the next thing to do is to not only try to look at each graph up to isomorphism once, but to somehow generate them in an order that makes it likely that you find cliques or independent sets early. Thereby letting you prune out big chunks of the search space. With the ability to start different computers out in different ranges so we can parallelize the search. But by now we're well down on the path to something that is very much not a naive search.