Van der Waerden number

From HandWiki

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

There are two cases in which the van der Waerden number W(r, k) is easy to compute: first, when the number of colors r is equal to 1, one has W(1, k) = k for any integer k, since one color produces only trivial colorings RRRRR...RRR (for the single color denoted R). Second, when the length k of the forced arithmetic progression is 2, one has W(r, 2) = r + 1, since one may construct a coloring that avoids arithmetic progressions of length 2 by using each color at most once, but using any color twice creates a length-2 arithmetic progression. (For example, for r = 3, the longest coloring that avoids an arithmetic progression of length 2 is RGB.) There are only seven other van der Waerden numbers that are known exactly. The table below gives exact values and bounds for values of W(r, k); values are taken from Rabung and Lotts except where otherwise noted.[1]

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,741[6]   >98,748  
6 1,132[7] >11,191   >157,209[8]   >786,740[8]   >1,555,549[8]  
7 >3,703   >48,811   >2,284,751[8]   >15,993,257[8]   >111,952,799[8]  
8 >11,495   >238,400   >12,288,155[8]   >86,017,085[8]   >602,119,595[8]  
9 >41,265   >932,745   >139,847,085[8]   >978,929,595[8]   >6,852,507,165[8]  
10 >103,474   >4,173,724   >1,189,640,578[8]   >8,327,484,046[8]   >58,292,388,322[8]  
11 >193,941   >18,603,731   >3,464,368,083[8]   >38,108,048,913[8]   >419,188,538,043 [8]  

Some lower bound colorings computed using SAT approach by Marijn J.H. Heule [6] can be found on github project page.

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

[math]\displaystyle{ W(r,k)\le 2^{2^{r^{2^{2^{k+9}}}}} }[/math]

as proved by Gowers.[9]

For a prime number p, the 2-color van der Waerden number is bounded below by

[math]\displaystyle{ p\cdot2^p\le W(2,p+1), }[/math]

as proved by Berlekamp.[10]

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

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

See also

References

  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). doi:10.37236/2363. http://www.combinatorics.org/ojs/index.php/eljc/article/view/2363. 
  2. 2.00 2.01 2.02 2.03 2.04 2.05 2.06 2.07 2.08 2.09 2.10 Chvátal, Vašek (1970). "Combinatorial Structures and Their Applications.". in Guy, Richard; Hanani, Haim; Sauer, Norbert et al.. Combinatorial Structures and Their Applications.. New York: Gordon and Breach. pp. 31–33. 
  3. 3.0 3.1 3.2 3.3 3.4 3.5 3.6 Beeler, Michael D.; O'Neil, Patrick E. (1979). "Some new van der Waerden numbers". Discrete Mathematics 28 (2): 135–146. doi:10.1016/0012-365x(79)90090-6. 
  4. 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 Kouril, Michal (2012). "Computing the van der Waerden number W(3,4)=293". Integers 12: A46. 
  5. 5.0 5.1 Stevens, Richard S.; Shantaram, R. (1978). "Computer-generated van der Waerden partitions". Mathematics of Computation 32 (142): 635–636. doi:10.1090/s0025-5718-1978-0491468-x. 
  6. 6.0 6.1 Heule, MarijnJ (2017). "Avoiding triples in arithmetic progression". Journal of Combinatorics 8: 391-422. https://www.cs.cmu.edu/~mheule/publications/JOC_08_03_A01.pdf. 
  7. 7.0 7.1 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. http://projecteuclid.org/euclid.em/1227031896. 
  8. 8.00 8.01 8.02 8.03 8.04 8.05 8.06 8.07 8.08 8.09 8.10 8.11 8.12 8.13 8.14 8.15 8.16 8.17 Monroe, Daniel (2019). "New Lower Bounds for van der Waerden Numbers Using Distributed Computing". arXiv:1603.03301 [math.CO].
  9. 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. http://www.dpmms.cam.ac.uk/~wtg10/sz898.dvi. 
  10. Berlekamp, E. (1968). "A construction for partitions which avoid long arithmetic progressions". Canadian Mathematical Bulletin 11 (3): 409–414. doi:10.4153/CMB-1968-047-7. 
  11. 11.00 11.01 11.02 11.03 11.04 11.05 11.06 11.07 11.08 11.09 11.10 11.11 Landman, Bruce; Robertson, Aaron; Culver, Clay (2005). "Some New Exact van der Waerden Numbers". Integers 5 (2): A10. http://www.emis.de/journals/INTEGERS/papers/a10int2003/a10int2003.pdf. 
  12. 12.0 12.1 12.2 12.3 12.4 12.5 12.6 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.
  13. 13.0 13.1 Ahmed, Tanbir (2010). "Two new van der Waerden numbers w(2;3,17) and w(2;3,18)". Integers 10 (4): 369–377. doi:10.1515/integ.2010.032. 
  14. 14.0 14.1 Ahmed, Tanbir; Kullmann, Oliver; Snevily, Hunter (2014). "On the van der Waerden numbers w(2;3,t)". Discrete Applied Mathematics 174 (2014): 27–51. doi:10.1016/j.dam.2014.05.007. 
  15. 15.0 15.1 15.2 15.3 Kouril, Michal (2015). "Leveraging FPGA clusters for SAT computations". Parallel Computing: On the Road to Exascale: 525–532. 
  16. Beeler, Michael D. (1983). "A new van der Waerden number". Discrete Applied Mathematics 6 (2): 207. doi:10.1016/0166-218x(83)90073-2. 
  17. 17.0 17.1 17.2 17.3 Ahmed, Tanbir (2012). "On computation of exact van der Waerden numbers". Integers 12 (3): 417–425. doi:10.1515/integ.2011.112. 
  18. 18.00 18.01 18.02 18.03 18.04 18.05 18.06 18.07 18.08 18.09 18.10 18.11 18.12 18.13 18.14 18.15 18.16 18.17 18.18 18.19 18.20 18.21 18.22 18.23 18.24 18.25 18.26 Ahmed, Tanbir (2013). "Some More Van der Waerden numbers". Journal of Integer Sequences 16 (4): 13.4.4. 
  19. 19.00 19.01 19.02 19.03 19.04 19.05 19.06 19.07 19.08 19.09 19.10 Brown, T. C. (1974). "Some new van der Waerden numbers (preliminary report)". Notices of the American Mathematical Society 21: A-432. 
  20. 20.00 20.01 20.02 20.03 20.04 20.05 20.06 20.07 20.08 20.09 20.10 20.11 20.12 20.13 20.14 20.15 20.16 20.17 20.18 20.19 20.20 20.21 20.22 20.23 20.24 20.25 20.26 20.27 20.28 20.29 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. 
  21. Schweitzer, Pascal (2009). Problems of Unknown Complexity, Graph isomorphism and Ramsey theoretic numbers (Ph.D. thesis). U. des Saarlandes.
  22. Shelah, Saharon (1988). "Primitive recursive bounds for van der Waerden numbers". Journal of the American Mathematical Society 1 (3): 683–697. doi:10.2307/1990952. 

Further reading

External links