Browse Groups

• ## [Computational Complexity] W(6,2) = 1132! (excitment, not factorial)

(1)
• NextPrevious
• 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
Message 1 of 1 , Jul 19, 2007
View Source
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 c-color 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).
1. VDW(3,2)=9, (easy)
2. VDW(3,3)=27, (Chvtal, 1970, math review entry,
3. VDW(3,4)=76, (Brown, Some new VDW numbers (prelim report), Notices of the AMS, Vol 21, (1974), A-432.
4. VDW(4,2)=35, Chvtal ref above
6. 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
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.