(An exposition of Nash-Williams's proof of the Kruskal Tree Theorem is here)
Andrew Vazsonyi (the mathematician, see here, not the folklorist, see here for that folklorist's wife) conjectured that the set of trees, under the minor ordering, is a well quasi order. I do not know when he made the conjecture, but he was born in 1916 and the conjecture was solved in 1960, so you can take a guess based on that. We only know he conjectured it since when Joe Kruskal proved it, he credits Vazsonyi and calls it `Vazonyi's conjecture' I do not know if anyone else ever called it that.
After a conjecture is solved it's usually called by the solvers name, not the poser's name, so it's hard to find out anything about Vazsonyi's conjecture when it was a conjecture.
Joe Kruskal's proof was quite hard and quite deep (are they necc the same? Prob not). See here for that paper. Nash-Williams three years later, in 1963, provided a much easier, though still deep proof. (I could not find a free online copy to point to- if you know of one please email me or comment.) Nash-Williams prove is in my writeup.
Joe Kruskal is Clyde Kruskal's uncle (Joe is also known in our circles for MST). I told Clyde that I made his Uncle's Theorem a problem on my TAKE HOME midterm in graduate Ramsey Theory. He PONDERED- is it sad that this once great theorem is now merely a problem in a course?
I asked some random students from both my Ramsey Theory class and my Aut theory class for their take on this. Here are the responses.
Dolapo: (Aut Student) Clyde should stop worrying about his Uncle's legacy and start building his own!
Ben: (Ramsey Student) Bill proved in class that SUBSEQUENCE is a wqo. GIVEN that, the problem wasn't that hard. Had he not given it to us the problem would be impossible.
Clyde: Bill, next time you teach the course give them the problem cold- without any prior theorems about wqo.
Bill: I'd rather not
Nishant:(Ramsey Student) Clyde should be happy, and know it, and clap his hands! People are still talking about his Uncle's Theorem!
Bill: If you're happy and you know it clap your hands! Alice is not clapping here hands. Bob is. What can you deduce about Alice and Bob? Never mind, that will be a different post.
Bill: If I gave the problem on an in-class exam in a grad course or a take-home exam in an ugrad course THEN you should be sad. But take-home exam in grad-course. That's just right.
Ben: (Ramsey Student) When are you going to do a post about this?
Bill: Since my post will include a pointer to a proof of the Kruskal Tree Theorem, I won't post until after you all hand in your take-home midterms.
Nishant and Ben together: Darn!
Joshua (TA for Aut Theory): I heard the grad students complaining about the problem being too hard is a sign of a great mathematician. If your grad students complain then kudos to Joe Kruskal!
Bill: They Didn't comlain
Clyde: Darn!
Ajeet (Ramsey Student) It's much harder to CREATE new math then to LEARN new math. I feel our working out this problem, given what you already gave us, was more a LEARNING thing rather than a CREATE thing. Like P vs NP: easier to verify then generate.
Katherine (Ramsey Student and Clydes Algorithms TA): A bigger problem for Joe Kruskal's legacy is that people in the algorithms class refer to The Kruskal MST algorithm as Clyde's Algorithm.
Saadiq (Aut Theory Student) If Clyde can test on Kruskal MST on his final (which he did) then you can test on Kruskal Tree theorem on your midterm (which you did).
Anyway, one lesson here is that fame is fleeting. Very few people are remembered 100 years after their death. So Clyde - I am helping keep your Uncle's memory alive!
Clyde: Oh Joy
SO- what do you think? Should Clyde be happy that his Uncle's theorem is on my take him midterm? Should he know it? Should he clap his hands?
Record for typos in a blog post? Should we be concerned about Bill?
ReplyDelete