[Computational Complexity] A "well known" theorem
- In the excellent paper On the power of two, three, and four probes
It is well known that every graph with s vertices and at least 2s edges contains a cycle of length at most 2log sMy students puzzled over this one in two ways. (1) How to prove it? Two of them came up with correct proofs that were not that hard. (2) Is it really well known? Two of them searched the web for a proof. They could not find one.
The problem with the phrase It is well known that is that it may be well known to people who know it (duh) but not to others. People not in the know don't even know if its hard or not (its not). Perhaps they should have said It is easy to show that. Or give a hint to the proof.
I invite my readers to give proofs to see if they differ from my students, and also so that the next time someone needs to reference this, they can point to this blog and attibute it to some cute alias.
A student asked me if giving as a reference a blog site or an unpublished paper on line is legit. I would say its more legit then giving as a reference a paper that is not on-line. A paper that is refereed but not online had a few people look at it closely. A paper that is unrefereed but online might have a lot more people look at it (then again, it might not). But since the reader can access it, he or she might be able to tell for himself or herself whether the statement they need has been proven properly.
Posted By GASARCH to Computational Complexity at 11/17/2008 12:16:00 PM