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, in January 2017, another mathematician, Harald 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 professional mathematicians too. (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.
In the comments, tell me about a time you struggled with a problem. What did you do to solve the problem? Did the struggle help the next time you had a similar problem?
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, in January 2017, another mathematician, Harald 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 professional mathematicians too. (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.
In the comments, tell me about a time you struggled with a problem. What did you do to solve the problem? Did the struggle help the next time you had a similar problem?
I still have to revisit this--even in the webwork 4. It helps me find circuits in trees.
ReplyDeleteGraph Theory was super confusing in the beginning. Especially trying to find Euler circuits. I started using my mini dry erase board to draw out my problems and erase the edges as I went along. It made it much more clear for me and I finally understood it. - Annaleece Lackey 110E Sec. 7
ReplyDeleteThat's a really good idea to use your mini dry erase board.
Deletegraph theory was hard at first. Just trying to get Euler paths and all of the others made it difficult to keep track of what goes with what. Eventually i got the hang of most of the definitions down in my head. Also going to the CAS and seeing how what the answer was suppose to be helped me further understand what i was doing wrong and how to fix it. i can't say graph theory is completely under my belt but I'm getting close.
ReplyDeletemarquese jackson
Good! :)
DeleteThat's great! The CAS worksheets are an excellent extra resource.
ReplyDeleteIt's a good skill to be able to find resources to help you solve a problem. Don't forget about the resources at placement.missouriwestern.edu, too.
ReplyDeleteGraph theory has been tricky for me. Although there are solutions to figuring out the answers, i can’t seem to detangle the graphs and still make them work. I have taken this class before and still feel like I can not fully grasp the concept of graph theory.
ReplyDelete