tag:blogger.com,1999:blog-3722233.post7575661419458429605..comments2024-08-02T19:37:12.269-05:00Comments on Computational Complexity: More on VDW over the RealsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-53871849193272402732007-12-20T17:22:00.000-06:002007-12-20T17:22:00.000-06:00With regards to fixing the proof for 3 and 7 both ...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61133581690116450292007-12-19T19:39:00.000-06:002007-12-19T19:39:00.000-06:00to fix the proofassume 3 & 7 red.If 5 = R then 3,5...to fix the proof<BR/><BR/>assume 3 & 7 red.<BR/>If 5 = R then 3,5,7 else 5=B<BR/>if 4=B and 6=B then 4,5,6 else 4 or 6 = R, let's say 4.<BR/>if 2=R then 2,3,4 else 2=B<BR/>if 8=B then 2,5,8, else 8=R<BR/>if 6=R then 6,7,8, else 6=B<BR/>if 9=R then 7,8,9 else 9=B<BR/>if 1=R then 1,4,7 else 1=B<BR/>1,5,9Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7326390632315678822007-12-19T18:26:00.000-06:002007-12-19T18:26:00.000-06:00The nice thing about VDWR is that VDW on the point...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.<BR/><BR/>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. <BR/><BR/>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 hopeAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-35283226860294842522007-12-19T16:37:00.000-06:002007-12-19T16:37:00.000-06:00>If 3,7 are RED then either 1 is RED and we're don...>If 3,7 are RED then either 1 is RED and we're done<BR/><BR/>How exactly is 1,3,7 an arithmetic progression?<BR/><BR/>-Johntromphttps://www.blogger.com/profile/16161842727664839561noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73114485165699939542007-12-19T15:06:00.000-06:002007-12-19T15:06:00.000-06:00What's with this whole VDW obsession? I can't even...What's with this whole VDW obsession? I can't even remember the last time there was a post about computational complexity.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82921937982908159932007-12-19T08:14:00.000-06:002007-12-19T08:14:00.000-06:00Nevermind! I hadn't seen that abbreviation before....Nevermind! I hadn't seen that abbreviation before.<BR/><BR/>http://en.wikipedia.org/wiki/Van_der_Waerden%27s_theoremAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-69187186064698202682007-12-19T08:11:00.000-06:002007-12-19T08:11:00.000-06:00Could you define VDW?Could you define VDW?Anonymousnoreply@blogger.com