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

[Computational Complexity] More on VDW over the Reals

Expand Messages
  • Lance
    Some of the comments made on the posts on this post on a VDW over the Reals been very enlightening to me about some math questions. In THIS post I will
    Message 1 of 1 , Dec 19, 2007
    • 0 Attachment
      Some of the comments made on the posts on this post on a VDW over the Reals been very enlightening to me about some math questions. In THIS post I will reiterate them to clarify them for myself, and hopefully for you.

      I had claimed that the proof that if you 2-color R you get a monochromatic 3-AP USED properties of R- notably that the midpoint of two elements of R is an element of R. Someone named ANONYMOUS (who would have impressed me if I knew who she was) left a comment pointed out that the proof works over N as well. THIS IS CORRECT:

      If you 2-color {1,...,9} then there will be a mono 3-AP. Just look at {3,5,7}. Two of them are the same color.

      1. If 3,5 are RED then either 1 is RED and we're done, 4 is RED and we're done, or 7 is RED and we're done, or 1,4,7 are all BLUE and we're done.
      2. If 5,7 are RED then either 3 is RED and we're done, or 6 is RED and we're done, or 9 is RED and we're done, or 3,6,9 are all BLUE, and we're done.
      3. If 3,7 are RED then either 1 is RED and we're done, or 5 is RED and we're done, or 9 is RED and we're done, or 1,5,9 are BLUE and we're done.
      This is INTERESTING (at least to me) since VDW(3,2)=9 is TRUE and this is a nice proof that VDW(3,2)\le 9. (Its easy to show VDW(3,2)\ne 8: take the coloring RRBBRRBB.)I had asked if VDWr may have an easier proof then VDW. Andy D (Andy Drucker who has his own Blog) pointed out that this is unlikely since there is an easy proof that VDWR--> VDW. Does this make VDWr more interesting or less interesting? Both!
      1. More Interesting:If VDWr is proven true using analysis or logic, then we get a NEW proof of VDW!
      2. Less Interesting: Since it is unlikely to get a new proof of VDW, it is likely that there is a proof of VDWr using analysis.


      --
      Posted By Lance to Computational Complexity at 12/19/2007 07:09:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.