Van der Waerden number

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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).

Tables of Van der Waerden numbers[edit]

There are two cases in which the van der Waerden number is easy to compute: first, W(1,k)=k for any integer k, since one color produces only trivial colorings RRRRR...RRR (for the single color denoted R). Second, 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 seven other van der Waerden numbers that are known exactly. Bounds in this table taken from Rabung and Lotts[1] except where otherwise noted.


k\r 2 colors 3 colors 4 colors 5 colors 6 colors
3 9[2] 27[2]   76[3]   >170   >223  
4 35[2] 293[4]   >1,048   >2,254   >9,778  
5 178[5] >2,173   >17,705   >98,740   >98,748  
6 1,132[6] >11,191   >91,331   >540,025   >816,981  
7 >3,703   >48,811   >420,217   >1,381,687   >7,465,909  
8 >11,495   >238,400   >2,388,317   >10,743,258   >57,445,718  
9 >41,265   >932,745   >10,898,729   >79,706,009   >458,062,329[7]
10 >103,474   >4,173,724   >76,049,218   >542,694,970[7] >2,615,305,384[7]
11 >193,941   >18,603,731   >305,513,57[7] >2,967,283,511[7] >3,004,668,671[7]


Van der Waerden numbers with r ≥ 2 are bounded above by

W(r,k)\le 2^{2^{r^{2^{2^{k+9}}}}}

as proved by Gowers.[8]

2-color van der Waerden numbers are bounded below by

p\cdot2^p\le W(2,p+1)

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

One sometimes also writes w(r; 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 W(r, k) = w(r; k, k, ..., k). Following is a list of some known van der Waerden numbers:

Known van der Waerden numbers
w(r;k1, k2, …, kr) Value Reference

w(2; 3,3)

9

Chvátal [2]

w(2; 3,4) 18 Chvátal [2]
w(2; 3,5) 22 Chvátal [2]
w(2; 3,6) 32 Chvátal [2]
w(2; 3,7) 46 Chvátal [2]
w(2; 3,8) 58 Beeler and O'Neil [3]
w(2; 3,9) 77 Beeler and O'Neil [3]
w(2; 3,10) 97 Beeler and O'Neil [3]
w(2; 3,11) 114 Landman, Robertson, and Culver [10]
w(2; 3,12) 135 Landman, Robertson, and Culver [10]
w(2; 3,13) 160 Landman, Robertson, and Culver [10]
w(2; 3,14) 186 Kouril [11]
w(2; 3,15) 218 Kouril [11]
w(2; 3,16) 238 Kouril [11]
w(2; 3,17) 279 Ahmed [12]
w(2; 3,18) 312 Ahmed [12]
w(2; 3,19) 349 Ahmed, Kullmann, and Snevily [13]
w(2; 4,4) 35 Chvátal [2]
w(2; 4,5) 55 Chvátal [2]
w(2; 4,6) 73 Beeler and O'Neil [3]
w(2; 4,7) 109 Beeler [14]
w(2; 4,8) 146 Kouril [11]
w(2; 4,9) 309 Ahmed [15]
w(2; 5,5) 178 Stevens and Shantaram [5]
w(2; 5,6) 206 Kouril [11]
w(2; 5,7) 260 Ahmed [16]
w(2; 6,6) 1132 Kouril and Paul [6]
w(3; 2, 3, 3) 14 Brown [17]
w(3; 2, 3, 4) 21 Brown [17]
w(3; 2, 3, 5) 32 Brown [17]
w(3; 2, 3, 6) 40 Brown [17]
w(3; 2, 3, 7) 55 Landman, Robertson, and Culver [10]
w(3; 2, 3, 8) 72 Kouril [11]
w(3; 2, 3, 9) 90 Ahmed [18]
w(3; 2, 3, 10) 108 Ahmed [18]
w(3; 2, 3, 11) 129 Ahmed [18]
w(3; 2, 3, 12) 150 Ahmed [18]
w(3; 2, 3, 13) 171 Ahmed [18]
w(3; 2, 3, 14) 202 Kouril [4]
w(3; 2, 4, 4) 40 Brown [17]
w(3; 2, 4, 5) 71 Brown [17]
w(3; 2, 4, 6) 83 Landman, Robertson, and Culver [10]
w(3; 2, 4, 7) 119 Kouril [11]
w(3; 2, 4, 8) 157 Kouril [4]
w(3; 2, 5, 5) 180 Ahmed [18]
w(3; 2, 5, 6) 246 Kouril [4]
w(3; 3, 3, 3) 27 Chvátal [2]
w(3; 3, 3, 4) 51 Beeler and O'Neil [3]
w(3; 3, 3, 5) 80 Landman, Robertson, and Culver [10]
w(3; 3, 3, 6) 107 Ahmed [15]
w(3; 3, 4, 4) 89 Landman, Robertson, and Culver [10]
w(3; 4, 4, 4) 293 Kouril [4]
w(4; 2, 2, 3, 3) 17 Brown [17]
w(4; 2, 2, 3, 4) 25 Brown [17]
w(4; 2, 2, 3, 5) 43 Brown [17]
w(4; 2, 2, 3, 6) 48 Landman, Robertson, and Culver [10]
w(4; 2, 2, 3, 7) 65 Landman, Robertson, and Culver [10]
w(4; 2, 2, 3, 8) 83 Ahmed [18]
w(4; 2, 2, 3, 9) 99 Ahmed [18]
w(4; 2, 2, 3, 10) 119 Ahmed [18]
w(4; 2, 2, 3, 11) 141 Schweitzer [19]
w(4; 2, 2, 4, 4) 53 Brown [17]
w(4; 2, 2, 4, 5) 75 Ahmed [18]
w(4; 2, 2, 4, 6) 93 Ahmed [18]
w(4; 2, 2, 4, 7) 143 Kouril [4]
w(4; 2, 3, 3, 3) 40 Brown [17]
w(4; 2, 3, 3, 4) 60 Landman, Robertson, and Culver [10]
w(4; 2, 3, 3, 5) 86 Ahmed [18]
w(4; 3, 3, 3, 3) 76 Beeler and O'Neil [3]
w(5; 2, 2, 2, 3, 3) 20 Landman, Robertson, and Culver [10]
w(5; 2, 2, 2, 3, 4) 29 Ahmed [18]
w(5; 2, 2, 2, 3, 5) 44 Ahmed [18]
w(5; 2, 2, 2, 3, 6) 56 Ahmed [18]
w(5; 2, 2, 2, 3, 7) 72 Ahmed [18]
w(5; 2, 2, 2, 3, 8) 88 Ahmed [18]
w(5; 2, 2, 2, 3, 9) 107 Kouril [4]
w(5; 2, 2, 2, 4, 4) 54 Ahmed [18]
w(5; 2, 2, 2, 4, 5) 79 Ahmed [18]
w(5; 2, 2, 2, 4, 6) 101 Kouril [4]
w(5; 2, 2, 3, 3, 3) 41 Landman, Robertson, and Culver [10]
w(5; 2, 2, 3, 3, 4) 63 Ahmed [18]
w(6; 2, 2, 2, 2, 3, 3) 21 Ahmed [18]
w(6; 2, 2, 2, 2, 3, 4) 33 Ahmed [18]
w(6; 2, 2, 2, 2, 3, 5) 50 Ahmed [18]
w(6; 2, 2, 2, 2, 3, 6) 60 Ahmed [18]
w(6; 2, 2, 2, 2, 4, 4) 56 Ahmed [18]
w(6; 2, 2, 2, 3, 3, 3) 42 Ahmed [18]
w(7; 2, 2, 2, 2, 2, 3, 3) 24 Ahmed [18]
w(7; 2, 2, 2, 2, 2, 3, 4) 36 Ahmed [18]
w(7; 2, 2, 2, 2, 2, 3, 5) 55 Ahmed [15]
w(7; 2, 2, 2, 2, 2, 3, 6) 65 Ahmed [16]
w(7; 2, 2, 2, 2, 2, 4, 4) 66 Ahmed [16]
w(7; 2, 2, 2, 2, 3, 3, 3) 45 Ahmed [16]
w(8; 2, 2, 2, 2, 2, 2, 3, 3) 25 Ahmed [18]
w(8; 2, 2, 2, 2, 2, 2, 3, 4) 40 Ahmed [15]
w(8; 2, 2, 2, 2, 2, 2, 3, 5) 61 Ahmed [16]
w(8; 2, 2, 2, 2, 2, 2, 3, 6) 71 Ahmed [16]
w(8; 2, 2, 2, 2, 2, 2, 4, 4) 67 Ahmed [16]
w(8; 2, 2, 2, 2, 2, 3, 3, 3) 49 Ahmed [16]
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 3) 28 Ahmed [18]
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 4) 42 Ahmed [16]
w(9; 2, 2, 2, 2, 2, 2, 2, 3, 5) 65 Ahmed [16]
w(9; 2, 2, 2, 2, 2, 2, 3, 3, 3) 52 Ahmed [16]
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 31 Ahmed [16]
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) 45 Ahmed [16]
w(10; 2, 2, 2, 2, 2, 2, 2, 2, 3, 5) 70 Ahmed [16]
w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 33 Ahmed [16]
w(11; 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) 48 Ahmed [16]
w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 35 Ahmed [16]
w(12; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) 52 Ahmed [16]
w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 37 Ahmed [16]
w(13; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4) 55 Ahmed [16]
w(14; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 39 Ahmed [16]
w(15; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 42 Ahmed [16]
w(16; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 44 Ahmed [16]
w(17; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 46 Ahmed [16]
w(18; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 48 Ahmed [16]
w(19; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 50 Ahmed [16]
w(20; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3) 51 Ahmed [16]

Van der Waerden numbers are primitive recursive, as proved by Shelah;[20] in fact he proved that they are (at most) on the fifth level \mathcal{E}^5 of the Grzegorczyk hierarchy.

See also[edit]

References[edit]

  1. ^ Rabung, John; Lotts, Mark (2012). "Improving the use of cyclic zippers in finding lower bounds for van der Waerden numbers". Electron. J. Combin. 19 (2). MR 2928650. 
  2. ^ a b c d e f g h i j k Chvátal, Vašek (1970). "Some unknown van der Waerden numbers". In Guy, Richard; Hanani, Haim; Sauer, Norbert; et al. Combinatorial Structures and Their Applications. New York: Gordon and Breach. pp. 31–33. MR 0266891. 
  3. ^ a b c d e f g Beeler, Michael D.; O'Neil, Patrick E. (1979). "Some new van der Waerden numbers". Discrete Math. 28 (2): 135–146. doi:10.1016/0012-365x(79)90090-6. MR 0546646. 
  4. ^ a b c d e f g h Kouril, Michal (2012). "Computing the van der Waerden number W(3,4)=293". Integers 12: A46. MR 3083419. 
  5. ^ a b Stevens, Richard S.; Shantaram, R. (1978). "Computer-generated van der Waerden partitions". Math. Comp. 32: 635–636. doi:10.1090/s0025-5718-1978-0491468-x. MR 0491468. 
  6. ^ a b Kouril, Michal; Paul, Jerome L. (2008). "The Van der Waerden Number W(2,6) is 1132". Experimental Mathematics 17 (1): 53–61. doi:10.1080/10586458.2008.10129025. MR 2410115. 
  7. ^ a b c d e f "Daniel Monroe, Van Der Waerden Numbers". vdwnumbers.org. Retrieved 2015-09-19. 
  8. ^ Gowers, Timothy (2001). "A new proof of Szemerédi's theorem". Geom. Funct. Anal. 11 (3): 465–588. doi:10.1007/s00039-001-0332-9. MR 1844079. 
  9. ^ Berlekamp, E. (1968). "A construction for partitions which avoid long arithmetic progressions". Canadian Mathematical Bulletin 11: 409–414. doi:10.4153/CMB-1968-047-7. MR 0232743. 
  10. ^ a b c d e f g h i j k l Landman, Bruce; Robertson, Aaron; Culver, Clay (2005). "Some New Exact van der Waerden Numbers" (PDF). Integers 5 (2): A10. MR 2192088. 
  11. ^ a b c d e f g Kouril, Michal (2006). A Backtracking Framework for Beowulf Clusters with an Extension to Multi-Cluster Computation and Sat Benchmark Problem Implementation (Ph.D. thesis). University of Cincinnati.  line feed character in |title= at position 54 (help)
  12. ^ a b Ahmed, Tanbir (2010). "Two new van der Waerden numbers w(2;3,17) and w(2;3,18)". Integers 10: 369–377. doi:10.1515/integ.2010.032. MR 2684128. 
  13. ^ Ahmed, Tanbir; Kullmann, Oliver; Snevily, Hunter. "On the van der Waerden numbers w(2;3,t)". Discrete Appl. Math. 174 (2014): 27–51. arXiv:1102.5433. doi:10.1016/j.dam.2014.05.007. MR 3215454. 
  14. ^ Beeler, Michael D. (1983). "A new van der Waerden number". Discrete Applied Math. 6 (2): 207. doi:10.1016/0166-218x(83)90073-2. MR 0707027. 
  15. ^ a b c d Ahmed, Tanbir (2012). "On computation of exact van der Waerden numbers". Integers 12 (3): 417–425. doi:10.1515/integ.2011.112. MR 2955523. 
  16. ^ a b c d e f g h i j k l m n o p q r s t u v w x y z aa Ahmed, Tanbir (2013). "Some More Van der Waerden numbers". Journal of Integer Sequences 16 (4): 13.4.4. MR 3056628. 
  17. ^ a b c d e f g h i j k Brown, T. C. (1974). "Some new van der Waerden numbers (preliminary report)". Notices of the American Mathematical Society 21: A–432. 
  18. ^ a b c d e f g h i j k l m n o p q r s t u v w x y z aa ab ac ad Ahmed, Tanbir (2009). "Some new van der Waerden numbers and some van der Waerden-type numbers". Integers 9: A6. doi:10.1515/integ.2009.007. MR 2506138. 
  19. ^ Schweitzer, Pascal (2009). Problems of Unknown Complexity, Graph isomorphism and Ramsey theoretic numbers (Ph.D. thesis). U. des Saarlandes. 
  20. ^ Shelah, Saharon (1988). "Primitive recursive bounds for van der Waerden numbers". J. Amer. Math. Soc. 1 (3): 683–697. doi:10.2307/1990952. MR 929498. 

Further reading[edit]

External links[edit]