NumberDB$^\beta$ Advanced search Tags Tables Help Login
Van der Waerden numbers $w(r; k_1,\dots,k_r)$
edit · history · discussion · files · long url · Ramsey theory combinatorics sequence
Numbers
$r$
$k_1,\dots,k_r$ 
$w(r;k_1,\dots,k_r)$
2
3, 3:
9
comment: This value is due to Chvátal [1].
2
3, 4:
18
comment: This value is due to Chvátal [1].
2
3, 5:
22
comment: This value is due to Chvátal [1].
2
3, 6:
32
comment: This value is due to Chvátal [1].
2
3, 7:
46
comment: This value is due to Chvátal [1].
2
3, 8:
58
comment: This value is due to Beeler and O'Neil [2].
2
3, 9:
77
comment: This value is due to Beeler and O'Neil [2].
2
3, 10:
97
comment: This value is due to Beeler and O'Neil [2].
2
3, 11:
114
comment: This value is due to Landman, Robertson and Culver [3].
2
3, 12:
135
comment: This value is due to Landman, Robertson and Culver [3].
2
3, 13:
160
comment: This value is due to Landman, Robertson and Culver [3].
2
3, 14:
186
comment: This value is due to Kouril [4].
2
3, 15:
218
comment: This value is due to Kouril [4].
2
3, 16:
238
comment: This value is due to Kouril [4].
2
3, 17:
279
comment: This value is due to Ahmed [5].
2
3, 18:
312
comment: This value is due to Ahmed [5].
2
3, 19:
349
comment: This value is due to Ahmed, Kullmann and Snevily [6].
2
3, 20:
389
comment: Ahmed, Kullmann and Snevily conjectured this value [6]; Kouril verified it [7].
2
4, 4:
35
comment: This value is due to Chvátal [1].
2
4, 5:
55
comment: This value is due to Chvátal [1].
2
4, 6:
73
comment: This value is due to Beeler and O'Neil [2].
2
4, 7:
109
comment: This value is due to Beeler [8].
2
4, 8:
146
comment: This value is due to Kouril [4].
2
4, 9:
309
comment: This value is due to Ahmed [9].
2
5, 5:
178
comment: This value is due to Stevens and Shantaram [10].
2
5, 6:
206
comment: This value is due to Kouril [4].
2
5, 7:
260
comment: This value is due to Ahmed [11].
2
6, 6:
1132
comment: This value is due to Kouril and Paul [12].
3
2, 3, 3:
14
comment: This value is due to Brown [13].
3
2, 3, 4:
21
comment: This value is due to Brown [13].
3
2, 3, 5:
32
comment: This value is due to Brown [13].
3
2, 3, 6:
40
comment: This value is due to Brown [13].
3
2, 3, 7:
55
comment: This value is due to Landman, Robertson and Culver [3].
3
2, 3, 8:
72
comment: This value is due to Kouril [4].
3
2, 3, 9:
90
comment: This value is due to Ahmed [14].
3
2, 3, 10:
108
comment: This value is due to Ahmed [14].
3
2, 3, 11:
129
comment: This value is due to Ahmed [14].
3
2, 3, 12:
150
comment: This value is due to Ahmed [14].
3
2, 3, 13:
171
comment: This value is due to Ahmed [14].
3
2, 3, 14:
202
comment: This value is due to Kouril [15].
3
2, 4, 4:
40
comment: This value is due to Brown [13].
3
2, 4, 5:
71
comment: This value is due to Brown [13].
3
2, 4, 6:
83
comment: This value is due to Landman, Robertson and Culver [3].
3
2, 4, 7:
119
comment: This value is due to Kouril [4].
3
2, 4, 8:
157
comment: This value is due to Kouril [15].
3
2, 5, 5:
180
comment: This value is due to Ahmed [14].
3
2, 5, 6:
246
comment: This value is due to Kouril [15].
3
3, 3, 3:
27
comment: This value is due to Chvátal [1].
3
3, 3, 4:
51
comment: This value is due to Beeler and O'Neil [2].
3
3, 3, 5:
80
comment: This value is due to Landman, Robertson and Culver [3].
3
3, 3, 6:
107
comment: This value is due to Ahmed [9].
3
3, 4, 4:
89
comment: This value is due to Landman, Robertson and Culver [3].
3
4, 4, 4:
293
comment: This value is due to Kouril [15].
4
2, 2, 3, 3:
17
comment: This value is due to Brown [13].
4
2, 2, 3, 4:
25
comment: This value is due to Brown [13].
4
2, 2, 3, 5:
43
comment: This value is due to Brown [13].
4
2, 2, 3, 6:
48
comment: This value is due to Landman, Robertson and Culver [3].
4
2, 2, 3, 7:
65
comment: This value is due to Landman, Robertson and Culver [3].
4
2, 2, 3, 8:
83
comment: This value is due to Ahmed [14].
4
2, 2, 3, 9:
99
comment: This value is due to Ahmed [14].
4
2, 2, 3, 10:
119
comment: This value is due to Ahmed [14].
4
2, 2, 3, 11:
141
comment: This value is due to Schweitzer [16].
4
2, 2, 3, 12:
163
comment: This value is due to Kouril [7].
4
2, 2, 4, 4:
53
comment: This value is due to Brown [13].
4
2, 2, 4, 5:
75
comment: This value is due to Ahmed [14].
4
2, 2, 4, 6:
93
comment: This value is due to Ahmed [14].
4
2, 2, 4, 7:
143
comment: This value is due to Kouril [15].
4
2, 3, 3, 3:
40
comment: This value is due to Brown [13].
4
2, 3, 3, 4:
60
comment: This value is due to Landman, Robertson and Culver [3].
4
2, 3, 3, 5:
86
comment: This value is due to Ahmed [14].
4
2, 3, 3, 6:
115
comment: This value is due to Kouril [7].
4
3, 3, 3, 3:
76
comment: This value is due to Beeler and O'Neil [2].
5
2, 2, 2, 3, 3:
20
comment: This value is due to Landman, Robertson and Culver [3].
5
2, 2, 2, 3, 4:
29
comment: This value is due to Ahmed [14].
5
2, 2, 2, 3, 5:
44
comment: This value is due to Ahmed [14].
5
2, 2, 2, 3, 6:
56
comment: This value is due to Ahmed [14].
5
2, 2, 2, 3, 7:
72
comment: This value is due to Ahmed [14].
5
2, 2, 2, 3, 8:
88
comment: This value is due to Ahmed [14].
5
2, 2, 2, 3, 9:
107
comment: This value is due to Kouril [15].
5
2, 2, 2, 4, 4:
54
comment: This value is due to Ahmed [14].
5
2, 2, 2, 4, 5:
79
comment: This value is due to Ahmed [14].
5
2, 2, 2, 4, 6:
101
comment: This value is due to Kouril [15].
5
2, 2, 3, 3, 3:
41
comment: This value is due to Landman, Robertson and Culver [3].
5
2, 2, 3, 3, 4:
63
comment: This value is due to Ahmed [14].
5
2, 2, 3, 3, 5:
95
comment: This value is due to Kouril [7].
6
2, 2, 2, 2, 3, 3:
21
comment: This value is due to Ahmed [14].
6
2, 2, 2, 2, 3, 4:
33
comment: This value is due to Ahmed [14].
6
2, 2, 2, 2, 3, 5:
50
comment: This value is due to Ahmed [14].
6
2, 2, 2, 2, 3, 6:
60
comment: This value is due to Ahmed [14].
6
2, 2, 2, 2, 4, 4:
56
comment: This value is due to Ahmed [14].
6
2, 2, 2, 3, 3, 3:
42
comment: This value is due to Ahmed [14].
7
2, 2, 2, 2, 2, 3, 3:
24
comment: This value is due to Ahmed [14].
7
2, 2, 2, 2, 2, 3, 4:
36
comment: This value is due to Ahmed [14].
7
2, 2, 2, 2, 2, 3, 5:
55
comment: This value is due to Ahmed [9].
7
2, 2, 2, 2, 2, 3, 6:
65
comment: This value is due to Ahmed [11].
7
2, 2, 2, 2, 2, 4, 4:
66
comment: This value is due to Ahmed [11].
7
2, 2, 2, 2, 3, 3, 3:
45
comment: This value is due to Ahmed [11].
8
2, 2, 2, 2, 2, 2, 3, 3:
25
comment: This value is due to Ahmed [14].
8
2, 2, 2, 2, 2, 2, 3, 4:
40
comment: This value is due to Ahmed [9].
8
2, 2, 2, 2, 2, 2, 3, 5:
61
comment: This value is due to Ahmed [11].
8
2, 2, 2, 2, 2, 2, 3, 6:
71
comment: This value is due to Ahmed [11].
8
2, 2, 2, 2, 2, 2, 4, 4:
67
comment: This value is due to Ahmed [11].
8
2, 2, 2, 2, 2, 3, 3, 3:
49
comment: This value is due to Ahmed [11].
9
2, 2, 2, 2, 2, 2, 2, 3, 3:
28
comment: This value is due to Ahmed [14].
9
2, 2, 2, 2, 2, 2, 2, 3, 4:
42
comment: This value is due to Ahmed [11].
9
2, 2, 2, 2, 2, 2, 2, 3, 5:
65
comment: This value is due to Ahmed [11].
9
2, 2, 2, 2, 2, 2, 3, 3, 3:
52
comment: This value is due to Ahmed [11].
10
2, 2, 2, 2, 2, 2, 2, 2, 3, 3:
31
comment: This value is due to Ahmed [11].
10
2, 2, 2, 2, 2, 2, 2, 2, 3, 4:
45
comment: This value is due to Ahmed [11].
10
2, 2, 2, 2, 2, 2, 2, 2, 3, 5:
70
comment: This value is due to Ahmed [11].
11
2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3:
33
comment: This value is due to Ahmed [11].
11
2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4:
48
comment: This value is due to Ahmed [11].
12
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3:
35
comment: This value is due to Ahmed [11].
12
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4:
52
comment: This value is due to Ahmed [11].
13
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3:
37
comment: This value is due to Ahmed [11].
13
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4:
55
comment: This value is due to Ahmed [11].
14
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3:
39
comment: This value is due to Ahmed [11].
15
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3:
42
comment: This value is due to Ahmed [11].
16
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3:
44
comment: This value is due to Ahmed [11].
17
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3:
46
comment: This value is due to Ahmed [11].
18
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3:
48
comment: This value is due to Ahmed [11].
19
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3:
50
comment: This value is due to Ahmed [11].
20
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3:
51
comment: This value is due to Ahmed [11].
21
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3:
52
comment: This value is due to Karki [17].
Definition
The Van der Waerden number $w(r; k_1,\dots,k_r)$ is the least positive integer $N$ such that every coloring of $\{1,\dots,N\}$ with $r$ colors has, for some color $i$, a monochromatic arithmetic progression of length $k_i$ in color $i$ [18].
Parameters
$r$
—   number of colors ($r \geq 1$)
$k_1,\dots,k_r$
—   progression-length tuple (a weakly increasing comma-separated tuple of $r$ positive integers)
Formulas
(1)
$w(1;k)=k$.
(2)
$w(r;2,\dots,2)=r+1$.
(3)
For any permutation $\sigma$ of $\{1,\dots,r\}$, $w(r;k_{\sigma(1)},\dots,k_{\sigma(r)})=w(r;k_1,\dots,k_r)$.
Comments
(4)
The progression-length tuple is stored weakly increasing.
(5)
The diagonal notation $W(r,k)$ means $w(r; k,\dots,k)$.
(6)
Wikipedia's table of $W(r,k)$ [18] gives only lower bounds for further diagonal values, and a value known only from one side is not stored.
References
[1]
Vašek Chvátal, "Some unknown van der Waerden numbers", in Combinatorial Structures and Their Applications, Gordon and Breach, 31-33, 1970. (MR)
[2]
Michael D. Beeler and Patrick E. O'Neil, "Some new van der Waerden numbers", Discrete Mathematics 28 (2), 135-146, 1979. (doi) (MR)
[3]
Bruce M. Landman, Aaron Robertson and Clay Culver, "Some New Exact van der Waerden Numbers", Integers 5 (2), A10, 2005. (arXiv) (MR)
[4]
Michal Kouril, "A Backtracking Framework for Beowulf Clusters with an Extension to Multi-Cluster Computation and SAT Benchmark Problem Implementation", Ph.D. thesis, University of Cincinnati, 2006.
[5]
Tanbir Ahmed, "Two new van der Waerden numbers w(2;3,17) and w(2;3,18)", Integers 10 (4), 369-377, 2010. (doi) (MR)
[6]
Tanbir Ahmed, Oliver Kullmann and Hunter Snevily, "On the van der Waerden numbers w(2;3,t)", Discrete Applied Mathematics 174, 27-51, 2014. (arXiv) (doi) (MR)
[7]
Michal Kouril, "Leveraging FPGA clusters for SAT computations", Parallel Computing: On the Road to Exascale, 525-532, 2015.
[8]
Michael D. Beeler, "A new van der Waerden number", Discrete Applied Mathematics 6 (2), 207, 1983. (doi) (MR)
[9]
Tanbir Ahmed, "On computation of exact van der Waerden numbers", Integers 12 (3), 417-425, 2012. (doi) (MR)
[10]
Richard S. Stevens and R. Shantaram, "Computer-generated van der Waerden partitions", Mathematics of Computation 32 (142), 635-636, 1978. (doi) (MR)
[11]
Tanbir Ahmed, "Some More Van der Waerden numbers", Journal of Integer Sequences 16, Article 13.4.4, 2013. (MR)
[12]
Michal Kouril and Jerome L. Paul, "The Van der Waerden Number W(2,6) is 1132", Experimental Mathematics 17 (1), 53-61, 2008. (doi) (MR)
[13]
T. C. Brown, "Some new van der Waerden numbers (preliminary report)", Notices of the American Mathematical Society 21, A-432, 1974.
[14]
Tanbir Ahmed, "Some new van der Waerden numbers and some van der Waerden-type numbers", Integers 9, A6, 65-76, 2009. (doi) (MR)
[15]
Michal Kouril, "Computing the van der Waerden number W(3,4)=293", Integers 12, A46, 2012. (MR)
[16]
Pascal Schweitzer, "Problems of Unknown Complexity, Graph Isomorphism and Ramsey Theoretic Numbers", Ph.D. thesis, Universität des Saarlandes, 2009.
[17]
Sikij Karki, "A New van der Waerden Number", U(t)-Mathazine 9, 34-39, 2024.
Links
Similar tables
Diagonal Ramsey numbers —   also records least $N$ forcing a monochromatic structure, using cliques in two-colored complete graphs rather than arithmetic progressions in $\{1,\dots,N\}$
Ramsey numbers $R(k_1,\ldots,k_r)$ of complete graphs —   uses the same $r$-coloring threshold for complete subgraphs of $K_N$ rather than arithmetic progressions in $\{1,\dots,N\}$
Data properties
Entries are of type: integer
How well the digits are known: exact
Table is complete: no (it holds every exact value in Wikipedia's table of known van der Waerden numbers [18], diagonal and off-diagonal alike, and omits values known there only from one-sided bounds)
Sources of data: [18], [19]
How they were obtained:

The entries are exact integers transcribed from Wikipedia's table of known van der Waerden numbers [18]. Each entry comment cites the reference named by that source table. The diagonal exact values are checked against MathWorld [19].



API Python package Skill for AI Privacy Legal notice Source
Data licensed CC BY-SA 4.0. No tracking, no analytics, essential cookies only.