Van der Waerden number

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 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; k₁, k₂, ..., k_r) to mean the smallest number w such that any coloring of the integers { 1, 2, ..., w } with r colors contains a progression of length k_i 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

• Ramsey number

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). MR 2928650.
2. 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. 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. Kouril, Michal (2012). "Computing the van der Waerden number W(3,4)=293". Integers 12: A46. MR 3083419.
5. 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. 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. "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. Landman, Bruce; Robertson, Aaron; Culver, Clay (2005). "Some New Exact van der Waerden Numbers" (PDF). Integers 5 (2): A10. MR 2192088.
11. 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. 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. 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. Ahmed, Tanbir (2013). "Some More Van der Waerden numbers". Journal of Integer Sequences 16 (4): 13.4.4. MR 3056628.
17. Brown, T. C. (1974). "Some new van der Waerden numbers (preliminary report)". Notices of the American Mathematical Society 21: A–432.
18. 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

• 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. MR 3243507.
• 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). MR 2285810.

External links

• O'Bryant, Kevin and Weisstein, Eric W., "Van der Waerden Number", MathWorld.
• Ahmed, Tanbir. "Known van der Waerden Number".