Monday, November 17, 2008

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 s
My 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.


  1. This is related to the problem of the "Moore bound". The particular result stated here follows from a paper of Alon+Hoory+Linial: (I'm definitely not saying that's the easiest proof.)

    See, for example, page 10 of Diestel's book "Graph Theory", available on Google Books.

  2. Induction on s. If there exists a vertex of degree <= 2, we are done: removing such a vertex leads to s-1 vertices and at least 2(s-1) edges, and induction does it. Otherwise, the min degree is >= 3, and if we grow a tree starting at an arbitrary vertex, each node should lead to at least two yet-unexplored children, so we will get a cycle within depth log s -- so, cycle length <= 2 * depth <= 2 log s. Was this your proof? --aravind

  3. It is well known that is that it may be well known to people who know it (duh) but not to others.

    This reminds me a paper I saw once as a PC chair. It went out to four reviewers, two of them world-experts in the field, the other two familiar with the subject but not experts.

    The familiar-but-not-expert reviewers said the result was new and interesting, clear accept.

    The world-experts said: "this is well known, not worth publishing", clear reject.

    So question to the readers out there, what would should the decision be in this case: accept or reject?

  4. I'm sure I'm not following something here. Anonymous's proof doesn't seem to prove anything to me (but I might just not understand it) and this graph seems to disprove the original statement:
    (As pictured it's directed, but the result is the same if it's considered undirected and the cycle does not repeat an edge.)

    That graph should have a cycle of length 2(log 10) = 2 by the above statement, but it does not. I'm guessing either I'm missing something the definition of some term, or there's some context to the originally quoted statement that provides additional conditions. It's been a while since I touched graph theory, so I'm sure I screwed something up, but this will haunt me if I can't figure out HOW I'm wrong.

  5. Sorry, link was too long, here's a tiny URL:

  6. For sage: the base for the log function is 2.

  7. Kurt: Thanks :) For some reason I didn't consider that, I just checked it wasn't base e.

  8. I remember this being a homework exercise in undergraduate algorithms at Berkeley. Does that count as "well known"

  9. Sorry, but I've been holding back for a few months now so I'll just go ahead and ask, even if it's off-topic :)

    Is there some hidden reason why you keep saying its instead of it's?

  10. Hi,

    Does this work?

    Let v be the size of the largest cycle in the graph. We can create two cycles from this with an edge which splits it in two halfs. Each of these has size v/2. Any other edge insertion leads to a cycle of length less than v/2. And so we proceed, producing two cycles from each which are half it's size.

    Since we have at most s edges to add after the initial cycle, the min depth of this binary tree is log s.

    hmmmm, it's not quite finished ...

  11. This comment has been removed by the author.