Post #328

Some History on the Reconstruction Conjecture I already wrote about reconstruction conjecture (here and here) and must admit that it's my weakness: every so often you find some fact about it and continue falling down the rabbit hole. It's simplicity with sheer volume of possibilities is nothing like for any other problem. Two other good ones are graph isomorphism and P vs NP but those seem very hard to resolve, while for reconstruction conjecture you just need to get a pair of graphs as a counter-example — anyone can do it. It seemed that very few people tried to disprove it and a general opinion, as far as I can judge, was that the conjecture holds. However, I obtained a very amusing and insightful presentation of a mathematician Allen Schwenk, a PhD student of another prominent mathematician Frank Harary, who contributed a lot to this conjecture. In this presentation he explains why he strongly convinced that the conjecture is false. Here is a quote from our exchange that I think expresses the feeling of trying to solve the reconstruction conjecture: "...But I have returned to this problem every year for the past 43 years for at least 50 hours each year. I have tried maybe a hundred constructions, with no success. I think I have pondered this in bed as I fall asleep at least 1000 times. So either this demonstrates that my intended method is no good, or that I am not smart enough to make it work... I would like nothing more than to see this problem solved before I die. I still believe strongly that the conjecture is false, but possibly that examples are exponentially large.". Maybe some of my readers will solve it one day.