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 V(r,k).

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.[1] Bounds in this table taken from Herwig, et. al 2007[2] except where otherwise noted.

r\k 3 4 5 6 7 8
2 colors 9   35   178   1,132[3] ≥ 3,703   ≥ 11,495  
3 colors 27   ≥ 292   ≥ 1,210   ≥ 8,886   ≥ 43,855   ≥ 238,400  
4 colors 76   ≥ 1,048   ≥ 17,705   ≥ 91,331   ≥ 393,469  
5 colors ≥ 126   ≥ 2,254   ≥ 24,045   ≥ 246,956  
6 colors ≥ 207   ≥ 9,778   ≥ 63,473   ≥ 633,981  

One sometimes also writes w(k1, k2, ..., kr) to mean the smallest number w such that any coloring of the integers { 1, 2, ..., w } with r colors contains a progression of length ki 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.[4]

[edit] External links

[edit] References

  1. ^ Landman, Bruce; Aaron Robertson (Jan 2004). Ramsey Theory on the Integers. American Mathematical Society, 317. 
  2. ^ 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).
  3. ^ Kouril, M., Paul, J.L., "The Van der Waerden number W(2,6) is 1132". Experimental Mathematics 17(2008), 53-61.
  4. ^ 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., 80. ISBN 8173197318.