Friday, September 16, 2011

The hidden life of researchers

Recently I was looking at the paper "Finding hidden Hamiltonian cycles" by Broder, Frieze and Shamir. Take a random sparse graph (edge probability p=O(1)/n), and add a (hidden) Hamiltonian cycle to create the input graph. Can you then reconstruct some Hamiltonian cycle?

I found and downloaded the paper (a 2006 Random Structures and Algorithms paper, the child of a 1991 STOC paper) from Frieze's home page at CMU. I started reading it, and on page 6, surprise! I saw the following margin note:
"Are we off by one here? There can no be two triangles with a common endpoint, but [...] since the corresponding edges are not independent."
I immediately scanned the rest of the paper and found two other margin notes. Page 16, by Remark 2:
"Are we off by one here? See the side note on page 6",
and again on page 18:
"If the premise is true (see my previous side note) then it actually follows that [...]. Why? At first blush it seems that it should be [...] Is there a better argument?"

Thus we get a glimpse of how their collaboration works. The mystery question: who wrote that comment? I am betting on Alan Frieze. What a lovely expression, "at first blush", to describe a mathematical estimate!

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.