Friday, June 08, 2012

A new bound on 3-hypergraph Ramsey Number! Why wasn't it discovered earlier?


When a new result is first discovered one question to ask is Why wasn't it discovered earlier? We look at a result in Ramsey Theory from 2010 and speculate as to why it was not discovered earlier.

Let R(k) be the least n such that no matter how you 2-color the edges of the complete 3-hypergraph on R(k) vertices there will be a homogenous set of size k (that is, a set H of size k such that all 3-sets from H are the same color). R(k) is known to exist by Ramsey's theorem.

  1. Ramsey's original proof (in 1930) gave astronomical tower-like bounds on R(k).
  2. Erdos-Rado (1954) showed that R(k) is bounded by 224k.
  3. Conlon-Fox-Sudakov (2010) showed that R(k) is bounded by 222k. (They did a lot more in their paper- they looked at asymmetric 3-Hypergraph Ramsey Numbers and developed a new framework for them.) See Hypergraph Ramsey Numbers on that page.)
Why are these results important?
  1. An improvement on the 3-hypergraph Ramsey numbers automatically gives an improvement in the a-hypergraph Ramsey numbers for any a ≥ 3.
  2. There is an exponential gap between the upper and lower bounds of R(k) and all of the a-hypergraph Ramsey numbers. Hence any improvement may be a key to closing that gap.
I have (with Andy Parrish and Sandow Sanai) celebrated the result of CFS with a survey of bounds on the 3-hypergraph Ramsey Numbers here. Proofs and intuitions and historical context of the results enumerated above are in our survey. (If you read it and have corrections please email them to us- we plan to put it on arXiv next week.) The techniques in this paper did not depend on any mathematics unknown to Erdos or Rado (or others) in 1954. (This is in contrast to, say, Conlon's paper A New Upper Bound on Diagonal Ramsey Numbers which uses quasi random graphs- a technique and technology unknown in 1954.) So why didn't someone else prove the result earlier? Our speculations may apply to other results that are proven with techniques that were already known.
  1. The CFS paper develops a framework for upper bounds on asymmetric 3-Hypergraph Ramsey numbers that involving a game (not a FUN game, but a game). This framework is used to prove many things. If all you want is the bound on R(k) then you don't need the framework and you get a proof that, IN HINDSIGHT, gives you the bound in a way that Erdos-Rado could have done. That's alot of HINDSIGHT. (Our Survey gives the stripped down proof of just that result, without their game framework.)
  2. Not that many people worked on it. Hence that individual people didn't get it is not surprising. Perhaps Erdos-Rado was happy enough to get the bound from tower to merely 224k. More generally--- if an entire community is looking at a problem then the question Why wasn't it found earlier? may have a global answer. If its just a few people, it could just be local things like After working on this problem she switched to Computable Algebraic Topology.
  3. CFS are very very clever. This is another HINDSIGHT argument- AFTER its done it looks easy.
Other reasons that might apply in other cases, though not to the case at hand:
  1. Timing and Luck should not be underestimated. A paraphrase from The Honors Class: Hilbert's Problems and their Solvers, the chapter on Hilbert's 10th problem, page 112:
    All of these people, Robinson, Davis, Putnam, others had been reading Number Theory books full of obscure facts. Matiyasevich had just read the third edition of Nikolia Vorob'ev's ``popular book'' Fibonacci Numbers. In that book, published in 1969, there was a new result about the divisibility of Fibonacci numbers. Matiyasevich used it to prove If F(n)2 divides F(m) then F(n)divides m. This allowed him to solve Hilbert's 10th problem (building on work of Davis-Putnam-Robinson). Robinson had read that book, but not the third edition!
    With the web is this more or less likely to happen? I ask nonrhetorically. (The spelling I give for Matiyasevich is the one given in the book. I have seen different spellings.)
  2. Everyone thought the negation was true. This was one reason why NL=coNL was proven as late as it was.
  3. The problem itself wasn't looked at earlier. Some of the Time-Space tradeoffs for SAT may be in this category.
  4. A groupthink sets in and people are all thinking the same way. Laszlo Babai noted this concern in his 1990 article Email and the unexpected power of interaction where he writes:
    But will the diversity of thought that now exists be preserved in an era when intellectual fashions are dictated by the strongest? Shall we see more Levins and Razborovs come out of the Kolmogorov school, bringing in so prominently different, yet profoundly relevant ideas?
    He was referring to email, but the tendency of groupthink may be even more of a tendency with the web. (Levins and Razborovs, not Levin's and Razborov's, is how it appears in the original article.)
SO, READERS- your turn! Leave comments on results that, once proven, the question arose Why wasn't this proven earlier? and speculate as to why. You need not write a survey of the area.

3 comments:

  1. "... NL=coNL ..." you mean?

    ReplyDelete
    Replies
    1. Yes I meant NL=coNL.
      I have made the correction.

      NL=coNP would indeed be a surprise.
      If proven using known techniques it would fall into the category of not being discovered earlier since everyone thought it was false.

      Delete
  2. I recently solved a problem which had been open for a while in just a few days. Given the limitations of my technical skills, I'm pretty sure reason #2 was a major factor!

    ReplyDelete