Loading ...
Sorry, an error occurred while loading the content.

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

Expand Messages
  • GASARCH
    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
    • 0 Attachment
      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
      5. VDW(5,2)=178, Stevens and Shantarum, 1978 full article!
      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.