A PhD Student, Michal Kouril, found a new van der Waerden number,
W(2,6)=1132.
See
here for details. I had a list of known VDW numbers
in an earlier post, but I redo it here with the new result.
VDW(k,c) is the least number W such that no matter how you ccolor the elements {1,2,...,W} there will be k numbers equally spaced (e.g., 3,7,11,15) that are the same color. W(k,c) exists by VDW's Theorem. See
Wikipedia or
my post in Luca's blog
The only VDW numbers that are known are as follows: (see
this paper) by Landman, Robertson, Culver from 2005 and the website above about W(6,2).

VDW(3,2)=9, (easy)

VDW(3,3)=27, (Chvtal, 1970, math review entry,

VDW(3,4)=76, (Brown, Some new VDW numbers (prelim report), Notices of the
AMS, Vol 21, (1974), A432.

VDW(4,2)=35, Chvtal ref above

VDW(5,2)=178, Stevens and Shantarum, 1978 full article!

VDW(6,2)=1132. Michal Kouril. 2007. (Not available yet.)
Over email I had the following Q & A iwth Michal Kouril.
BILL: Why is it worth finding out?
MICHAL: As my advisor Jerry Paul put it
Why do we climb Mount Everest?"
Because it is there!
The advances we've made during the pursuit of W(6,2)
can have implications on other worthy problems.
BILL: Predict when we will get W(7,2)
MICHAL: Septemer 30, 2034. Or any time before or after.
Interest in Van der Waerden numbers has been growing lately and I would not
be surprised if we saw W(7,2) lot sooner than this. Some unknown
VDW numbers are already just a matter of the amount of
computing power you throw at them in order to prove the exact value.
But W(7,2) still need more analysis to make them provable in a
reasonable amount of time.
(Back to bill's blog:) In a perfect world Michal would
be interviewed by Steven Colbert instead of me.
Oh well...

Posted By GASARCH to
Computational Complexity at 7/19/2007 11:20:00 AM