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.
- 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.
- 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.
- 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.
- More Interesting: If VDWr is proven true using analysis or logic, then we get a NEW proof of VDW!
- 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.
Could you define VDW?
ReplyDeleteNevermind! I hadn't seen that abbreviation before.
ReplyDeletehttp://en.wikipedia.org/wiki/Van_der_Waerden%27s_theorem
What's with this whole VDW obsession? I can't even remember the last time there was a post about computational complexity.
ReplyDelete>If 3,7 are RED then either 1 is RED and we're done
ReplyDeleteHow exactly is 1,3,7 an arithmetic progression?
-John
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.
ReplyDeleteI'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
to fix the proof
ReplyDeleteassume 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
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