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]
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]
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:
| 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
- Ramsey number
- Graph coloring
References
- ↑ 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.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.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.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.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.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.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.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].
- ↑ 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.
- ↑ 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.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.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.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.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.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.
- ↑ 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.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.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.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.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.
- ↑ Schweitzer, Pascal (2009). Problems of Unknown Complexity, Graph isomorphism and Ramsey theoretic numbers (Ph.D. thesis). U. des Saarlandes.
- ↑ 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
- Landman, Bruce M.; Robertson, Aaron (2014). Ramsey Theory on the Integers. Student Mathematical Library. 73 (Second ed.). Providence, RI: American Mathematical Society. doi:10.1090/stml/073. ISBN 978-0-8218-9867-3.
- Herwig, P. R.; Heule, M. J. H.; van Lambalgen, P. M.; van Maaren, H. (2007). "A New Method to Construct Lower Bounds for Van der Waerden Numbers". The Electronic Journal of Combinatorics 14 (1). doi:10.37236/925. http://www.combinatorics.org/Volume_14/Abstracts/v14i1r6.html.
External links
- O'Bryant, Kevin. "Van der Waerden Number". http://mathworld.wolfram.com/vanderWaerdenNumber.html.
- Klarreich, Erica (2021-12-15). "Mathematician Hurls Structure and Disorder Into Century-Old Problem". https://www.quantamagazine.org/oxford-mathematician-advances-century-old-combinatorics-problem-20211215/.
 |  |
