Van der Waerden number

Van der Waerden's theorem states that for any positive integers "r" and "k" there exists a positive integer "N" such that if the integers {1, 2, ..., "N"} are colored, each with one of "r" different colors, then there are at least "k" integers in arithmetic progression all of the same color. The smallest such "N" is the van der Waerden number "V"("r","k"). Van der Waerden numbers are primitive recursive, as proved by Shelah; [Shelah, S. "Primitive Recursive Bounds for van der Waerden Numbers." "Journal of the American Mathematical Society" 1 (1988), pp. 683–697.] in fact he proved that they are (at most) on the fifth level $mathcal\{E\}^5$ of the Grzegorczyk hierarchy.

"V"(1,"k")="k" for any integer "k", since one color produces only trivial colorings RRRRR...RRR (for the single color denoted R). "V"("r",2)="r"+1, since we may construct a coloring that avoids arithmetic progressions of length 2 by using each color at most once, but once we use a color twice, a length 2 arithmetic progression is formed (e.g., for "r"=3, the longest coloring we can get that avoids an arithmetic progression of length 2 is RGB).

There are only a few known nontrivial van der Waerden numbers. Bounds in this table taken from Herwig, et. al 2007 [P.R. Herwig, M.J.H. Heule, P.M. van Lambalgen, H. van Maaren. " [http://www.combinatorics.org/Volume_14/Abstracts/v14i1r6.html A New Method to Construct Lower Bounds for Van der Waerden Numbers] ", "The Electronic Journal of Combinatorics" 14:1 (2007).] except where otherwise noted.

:

2-color van der Waerden numbers are bounded by:$(n-1)2^\{n-1\}le\; V(2,n)le\; 2^\{2^\{2^\{2^\{2^\{n+9\}$The left inequality holds for "n" − 1 prime, and is due to Berlekamp; [Berlekamp, E., "A construction for partitions which avoid long arithmetic progressions", "Canadian Mathematics Bulletin" 11 (1968), pp. 409–414.] the right inequality, which holds for all "n", is due to Timothy Gowers. [Gowers, W. T., "A new proof of Szemerédi's theorem", "Geometric and Functional Analysis" 11 (2001), pp. 465–588.]

One sometimes also writes "w"("k"₁, "k"₂, ..., "k"_"r") to mean the smallest number "w" such that any coloring of the integers { 1, 2, ..., "w" } with "r" colors contains a progression of length "k"_i of color "i", for some "i". Such numbers are called "off-diagonal van der Waerden numbers". Thus "V"("r", "k") = "w"("k", "k", ..., "k") with "r" arguments. "w"(4, 3, 3) is known to be exactly 51. [cite book |title=Discrete Mathematics And Its Applications |editor=M. Sethumadhavan |last=Brown | first=Tom C. | pages=80 | chapter=A partition of the non-negative integers, with applications to Ramsey theory |authorlink= |coauthors= |year=2006 |publisher=Alpha Science Int'l Ltd. |location= |isbn=8173197318 ]

External links

*MathWorld|title=Van der Waerden Number|urlname=vanderWaerdenNumber|author=O'Bryant, Kevin and Weisstein, Eric W.

References

*cite book
last = Landman
first = Bruce
coauthors = Aaron Robertson
title = Ramsey Theory on the Integers
publisher = American Mathematical Society
date = Jan 2004
pages = 317