Graph Isomorphisms and Making Mistakes

I've received several questions about problems 12 and 13 in the first WebWork graph theory assignment.  These questions give you a graph and ask you to determine which of the three graphs below is the same graph, represented differently.  It then asks you to give the one-to-one correspondence that identifies the two graphs.  This correspondence is called a graph isomorphism.  These problems can be tricky, and require some thought and creativity to find the right correspondence.  However, it's a valuable exercise to struggle with problems sometimes, and it makes finding the right solution all the more sweet!

Imagine if you had to do this same thing, but for a graph with thousands of vertices!  It might be a daunting task to imagine.  Of course, you wouldn't want to have to try to find this isomorphism by hand, but even asking a computer to do this would be difficult.  In fact, recent research has been trying to determine if there is a way to determine if two graphs are isomorphic "quickly".  A computer scientist, Laszlo Babai, from the University of Chicago, announced in November 2015 that he had found an algorithm to determine if two graphs were isomorphic in quasipolynomial time.  But, earlier this month, another mathematician,  Harold Helfgott, posted that he had found an error in the proof.  It can be frustrating for you to find that you've answered a problem incorrectly in MAT110(E); imagine if you had announced to all of your colleagues that you had solved a problem, only to find that your solution was incorrect.  This happens to mathematicians all the time.  (I, too, have submitted a paper to a mathematics journal claiming to have proven something, only to find that there was a subtle error in my reasoning.  I've still been unable to correct my error!)  Even when we get the answer wrong, there is value in the struggle that it takes to work with a problem.  Maybe those skills that you learned to work with this problem will help you with a problem in the future.  Maybe you'll remember how to correct it just a little bit better because you had to struggle to find the right answer.  Don't focus too much on worrying about making mistakes - everyone will make them - instead, make sure you learn from your mistakes and are ready to apply what you learned in the struggle to the next problem.

Don't worry about Babai - he's corrected the problem in his algorithm.

You can read more about graph isomorphisms and Laszlo Babai's algorithm at the American Mathematical Society's blog on math and the blog Computational Complexity.