5 ms·

It would require an advance in theory. When I took a graph theory course it fascinated me how the Ramsey theory problem goes from paper and pencil complexity to

by Cerium 6y ago

It would require an advance in theory. When I took a graph theory course it fascinated me how the Ramsey theory problem goes from paper and pencil complexity to beyond computing power in two steps (R(3,3) = 6, R(4,4) = 18, R(5,5)=(43..48?)). I once spent some time calculating the effort (but don't have the results handy), a rough number for a naive approach to exhaustively searching the problem space would involve something like 10^200 graphs.

btilly 6y ago
It is worse than that. Here is the calculation. The number of graphs of size n is 2^(n choose 2). (There are n choose 2 pairs of points, each of which could be or not be an edge.) If the answer is 43, that's 2^903 which is roughly 6.762 * 10^271. If the answer is 48, that's 2^1128 which is roughly 3.646 x 10^339. Naive plus better computers is not enough to tackle this problem.
- CrazyStat 6y ago
  >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.

by Cerium 6y ago

btilly 6y ago

It is worse than that. Here is the calculation. The number of graphs of size n is 2^(n choose 2). (There are n choose 2 pairs of points, each of which could be or not be an edge.) If the answer is 43, that's 2^903 which is roughly 6.762 * 10^271. If the answer is 48, that's 2^1128 which is roughly 3.646 x 10^339. Naive plus better computers is not enough to tackle this problem.

CrazyStat 6y ago
>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.