Loading ...
Sorry, an error occurred while loading the content.

994[Computational Complexity] If you get a new result of interest with little ef...

Expand Messages
    Jan 31, 2008
      Over the weekend I made an observation that gives a new (is it new?) lower bound on W(k,c). I will describe what all of this means, but my real interest are in the meta question if you have an easy proof of an interesting result, what to make of that?
      Van der Waerden's theorem: For all k, for all c, there exists W=W(k,c) such that for all c-colorings of {1,...,W} there exists a,d such that a, a+d, ..., a+(k-1)d are the same color.
      Chanda-Stockmeyer-Lipton showed (Lemma 4.4)
      If there exists A, a k-free set (a set with no arithmetic sequence of length k) that is a subset of [n], then there is a c-coloring of [n] with no monochromatic arithmetic sequence, where c=O((nlog n)/|A|).
      Laba and Lacey showed
      There is a constant a such that, for all k that is a power of 2, for all n, there is a k-free set of size n× exp(-a(log n)1/(log k). (There result is sharper than this but this will suffice for us. They acknowledge that the result was already known in 1960 by Rankin.)
      If you combine these two you obtain
      W(k,c) &ge exp((log c)&Omega(log k))
      I have looked at the literature and used google and this appears to be new. I seemed to have proven something new and interesting with very little effort. I pose questions that anyone should pose in this situation and answer them for my case.
      1. Is the result new? I think so- I've been looking at VDW papers for about 5 years now and have not run across it. Even so, would not be surprised (or even disappointed) if someone points to some paper I missed.
      2. Is the result interesting? YES Upper bounds on VDW have gotten alot of attention. Lower bounds less so, but some. And they are a nice check on upper bounds.
      3. Is the proof correct? In this case its just to easy to have gotten it wrong. (Famous last words...)
      4. Are the results you used not commonly known to the same people? While the Chandra et. al paper is not well known to combinatorics people, its the same principle as the Symmetric Hypergraph Lemma, which is known. However, the k-free set result is not that well known.
      5. Did the other people who knew all this stuff not care? Quite possible that the k-free set folks didn't care about this, or didn't think it was worth writing down.
      6. Are you connecting two areas that have not been connected before? NO- k-free sets were studied because of VDW theorem.
      7. What to do with the result? It deserves to be out there (for one thing, if I publicize it I may find out if its already known). I will probably write it up for a short note in some combinatorics journal (will check which ones take notes), and may put it on arXiv. Or might not bother hassling with referees (For more on that train of thought, see Zeilberg's opinion 77

      Posted By GASARCH to Computational Complexity at 1/31/2008 02:19:00 PM