Wednesday, December 19, 2007

More on VDW over the Reals

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)≤ 9. (Its easy to show VDW(3,2)≠ 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 unlikely that there is a proof of VDWr using analysis.

7 comments:

  1. Could you define VDW?

    ReplyDelete
  2. Nevermind! I hadn't seen that abbreviation before.

    http://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem

    ReplyDelete
  3. What's with this whole VDW obsession? I can't even remember the last time there was a post about computational complexity.

    ReplyDelete
  4. >If 3,7 are RED then either 1 is RED and we're done

    How exactly is 1,3,7 an arithmetic progression?

    -John

    ReplyDelete
  5. The nice thing about VDWR is that VDW on the points of a non-rectangular 2 or 3 dimensional grid can be gotten through the projection of the grid onto a line that's not orthogonal to any of the lines in the grid, and then that line can be converted to R. However it's easy to imagine that the projection would create irrational relationships between the line APs from different lines in the grid, which is why the line has to be in R and not N.

    I'm imagining that this is nice because I imagine that for a student the process of elimination on the grid might be easier to keep in their head then keeping track of the various intersections of the APs of different scales on just the line.

    Of course I should say that I am not 100% familiar with VDW and that this is all based on what I could imagine playing out, and may not be as close to reality as I would hope

    ReplyDelete
  6. to fix the proof

    assume 3 & 7 red.
    If 5 = R then 3,5,7 else 5=B
    if 4=B and 6=B then 4,5,6 else 4 or 6 = R, let's say 4.
    if 2=R then 2,3,4 else 2=B
    if 8=B then 2,5,8, else 8=R
    if 6=R then 6,7,8, else 6=B
    if 9=R then 7,8,9 else 9=B
    if 1=R then 1,4,7 else 1=B
    1,5,9

    ReplyDelete
  7. With regards to fixing the proof for 3 and 7 both red, yes the above post is a valid proof. However, the "nice" proof that Gasarch was going for appears to actually prove VDW(3,2)≤13 (replace 3, 5, 7 with 5, 7, 9 and do the analogous thing). So, as is often the case, a tight-and-elegant proof remains elusive.

    ReplyDelete