Van der Waerden number

From Wikipedia, the free encyclopedia

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 W(r,k). Van der Waerden numbers are primitive recursive, as proved by Shelah;^[1] in fact he proved that they are (at most) on the fifth level of the Grzegorczyk hierarchy.

W(1,k)=k for any integer k, since one color produces only trivial colorings RRRRR...RRR (for the single color denoted R). W(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 Heule 2008^[2] except where otherwise noted.

r\k	3	4	5	6	7	8
2 colors	9	35	178	1,132	> 3,703	> 11,495
3 colors	27	> 292	> 2,173	> 11,191	> 43,855	> 238,400
4 colors	76	> 1,048	> 17,705	> 91,331	> 393,469
5 colors	> 170	> 2,254	> 98,740	> 540,025
6 colors	> 207	> 9,778	> 98,748	> 633,981

Van der Waerden numbers with r ≥ 2 are bounded by

as proved by Timothy Gowers.^[3]

2-color van der Waerden numbers are bounded by

where p is prime, as proved by Berlekamp.^[4]

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 W(r, k) = w(k, k, ..., k) with r arguments. w(4, 3, 3) is known to be exactly 51.^[5]

[edit] References

1. ^ Shelah, S. "Primitive Recursive Bounds for van der Waerden Numbers." Journal of the American Mathematical Society 1 (1988), pp. 683–697.
2. ^ Marijn Heule, presentation at http://www.st.ewi.tudelft.nl/sat/slides/waerden.pdf
3. ^ Gowers, W. T., "A new proof of Szemerédi's theorem", Geometric and Functional Analysis 11 (2001), pp. 465–588.
4. ^ Berlekamp, E., "A construction for partitions which avoid long arithmetic progressions", Canadian Mathematics Bulletin 11 (1968), pp. 409–414.
5. ^ Brown, Tom C. (2006). "A partition of the non-negative integers, with applications to Ramsey theory". in M. Sethumadhavan. Discrete Mathematics And Its Applications. Alpha Science Int'l Ltd.. p. 80. ISBN 8173197318. 

• Landman, Bruce; Aaron Robertson (Jan 2004). Ramsey Theory on the Integers. American Mathematical Society. p. 317. 
• P.R. Herwig, M.J.H. Heule, P.M. van Lambalgen, H. van Maaren. "A New Method to Construct Lower Bounds for Van der Waerden Numbers", The Electronic Journal of Combinatorics 14:1 (2007).
• Kouril, M., Paul, J.L., "The Van der Waerden number W(2,6) is 1132". Experimental Mathematics 17 (2008), pp. 53–61.

[edit] External links

• O'Bryant, Kevin and Weisstein, Eric W., "Van der Waerden Number" from MathWorld.