- The posting idiot was a test case for the newly-fixed mechanism to email posts to people (some people had been getting this blog via email instead of going to the web.) It did not work. Nobody knows why.
-
I had written:
computers have gotten VDW(4,2) more complicated.
One of the comments was:For the "Ramsey-theory idiots" out there, the technical translation of VDW(4,2) is "I don't know exactly how much more complicated computers have gotten, but its a while hell of a lot!" :-)
The commenter is correct in clarifying what I meant; however, both the commentator and I are incorrect in the details. Inspired by the commenter, I looked up what is known about the VDW numbers. VDW(4,2) is known and is only 35. VDW(5,2) is known, and is only 178. I should have written VDW(5,5) which is unknown but quite likely quite large. - 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 is 4 numbers equally spaced) that are the same color. W(k,c) exists by van der Waerden's Theorem. See van der Waerden's Theorem-Wikipedia or van der Waerden's theorem-my posting in Luca's blog
-
I believe the only VDW numbers that are known are as follows: (see this paper) by Landman, Robertson, Culver from 2005.
- VDW(3,2)=9, (easy)
- VDW(3,3)=27, (Chvátal, 1970, math review entry, article not online.
- VDW(3,4)=76, (Brown, Some new van der Warden numbers (prelim report), Notices of the AMS, Vol 21, (1974), A-432. Article, review not online!
- VDW(4,2)=35, Chvátal ref above
- VDW(5,2)=178, Stevens and Shantarum, 1978 full article!
Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Google Analytics and Mathjax
Thursday, May 03, 2007
Coda to idiot-post
Coda to idiot.
Subscribe to:
Post Comments (Atom)
You'll use any excuse possible to talk VDW!!! =)
ReplyDelete--Yarden
what is "coda" mean?
ReplyDeleteIt's an alternative spelling of 'kudos'. Check it out at
ReplyDeletehttp://dictionary.reference.com/browse/coda