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).
- VDW(3,2)=9, (easy)
- VDW(3,3)=27, (Chvátal, 1970, math review entry,
- VDW(3,4)=76, (Brown, Some new VDW numbers (prelim report), Notices of the AMS, Vol 21, (1974), A-432.
- VDW(4,2)=35, Chvátal ref above
- VDW(5,2)=178, Stevens and Shantarum, 1978 full article!
- VDW(6,2)=1132. Michal Kouril. 2007. (Not available yet.)
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...
Please clarify: this is for 2 colors and six elements?
ReplyDeleteOr else what? Did you think 6 colors and 2 elements???
ReplyDeleteMaybe i'm missing something here, but isn't W(2,k)=k+1 trivialy true?
ReplyDeleteThe result is 2 colors,
ReplyDeleteyou want a sequence
of length 6. In my
notation that I defined
above W(6,2). I regard
the sequence length as
more important.
YES W(2,k)=k+1 is trivial.
This is not what was done.
1132 is much larger than one would be led to hope for with the most widely known elementary technique for avoiding long arithmetic progressions, namely, choosing the string randomly.
ReplyDeleteSo, my question for Michal Kouril would be: does your proof suggest generalizable ideas for the construction of these progression-avoiding strings?
Ya know, Anon 2, I'm not afraid of giving my real name while asking a stupid question -- unlike, um, some people, who #1) post anonymously and #2) "answer" a question by asking another question instead of taking a concrete position. Please note that my willingness to embrace public dopiness perhaps inspired commenter #3 to ask a question that was also "stupid" -- and now things are much clearer for a lot of us, not just me.
ReplyDeleteHave you ever done something nobody else ever did before without acting like a nitwit during the process? I haven't, and all the researchers, artists and business people I have talked to about this stuff have similar stories about having to crash through the "stupid wall" before coming up with something new.
I attended the most recent Midwest Theory Day. Do you know who asked the most (and "most obvious") questions? Lance Fortnow. In general, I think it's dumber to not ask the dumb question. As Bill asked in a recent post, which is bigger, your curiosity or your ego?
I agree that the comment of Anonymous #2 was rude and counterproductive.
ReplyDeleteRe: Andy D
ReplyDeleteShort answer is unfortunately No.
Some ideas for constructing long progression free strings are described in my paper with Dr. Franco "Resolution Tunnels for Improved SAT Solver Performance." Recently a number of people have been working on various ways to construct long progression free strings. In particular Marijn Heule, David Mitchell, ...