Van der Waerden number

Last updated December 09, 2024

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 numberW(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	>225
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

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

as proved by Gowers.^[9]

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

p\cdot 2^{p}\leq W(2,p+1),

as proved by Berlekamp.^[10]

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;k₁, k₂, …, k_r)	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]
w(21; 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3)	52	Karki^[22]

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

Related Research Articles

Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of the mathematical field of combinatorics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a question of the form: "how big must some structure be to guarantee that a particular property holds?"

Van der Waerden's theorem is a theorem in the branch of mathematics called Ramsey theory. Van der Waerden's theorem states that for any given positive integers r and k, there is some number 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 whose elements are of the same color. The least such N is the Van der Waerden number W(r, k), named after the Dutch mathematician B. L. van der Waerden.

Linnik's theorem in analytic number theory answers a natural question after Dirichlet's theorem on arithmetic progressions. It asserts that there exist positive c and L such that, if we denote p(a,d) the least prime in the arithmetic progression

In mathematics, analytic number theory is a branch of number theory that uses methods from mathematical analysis to solve problems about the integers. It is often said to have begun with Peter Gustav Lejeune Dirichlet's 1837 introduction of Dirichlet L-functions to give the first proof of Dirichlet's theorem on arithmetic progressions. It is well known for its results on prime numbers and additive number theory.

In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers A with positive natural density contains a k-term arithmetic progression for every k. Endre Szemerédi proved the conjecture in 1975.

In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory named after Alfred W. Hales and Robert I. Jewett, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial structure.

<span class="mw-page-title-main">Klaus Roth</span> British mathematician (1925–2015)

Klaus Friedrich Roth was a German-born British mathematician who won the Fields Medal for proving Roth's theorem on the Diophantine approximation of algebraic numbers. He was also a winner of the De Morgan Medal and the Sylvester Medal, and a Fellow of the Royal Society.

The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at each (triennial) International Symposium of the MOS. Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson to encourage mathematical excellence in the fields of research exemplified by his work. The prizes are now funded by an endowment administered by MPS.

A computer-assisted proof is a mathematical proof that has been at least partially generated by computer.

In Ramsey theory, a set S of natural numbers is considered to be a large set if and only if Van der Waerden's theorem can be generalized to assert the existence of arithmetic progressions with common difference in S. That is, S is large if and only if every finite partition of the natural numbers has a cell containing arbitrarily long arithmetic progressions having common differences in S.

Erdős' conjecture on arithmetic progressions, often referred to as the Erdős–Turán conjecture, is a conjecture in arithmetic combinatorics. It states that if the sum of the reciprocals of the members of a set A of positive integers diverges, then A contains arbitrarily long arithmetic progressions.

In computer science and formal methods, a SAT solver is a computer program which aims to solve the Boolean satisfiability problem. On input a formula over Boolean variables, such as "(x or y) and (x or not y)", a SAT solver outputs whether the formula is satisfiable, meaning that there are possible values of x and y which make the formula true, or unsatisfiable, meaning that there are no such values of x and y. In this case, the formula is satisfiable when x is true, so the solver should return "satisfiable". Since the introduction of algorithms for SAT in the 1960s, modern SAT solvers have grown into complex software artifacts involving a large number of heuristics and program optimizations to work efficiently.

Ergodic Ramsey theory is a branch of mathematics where problems motivated by additive combinatorics are proven using ergodic theory.

In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.

The arithmetic progression game is a positional game where two players alternately pick numbers, trying to occupy a complete arithmetic progression of a given size.

<span class="mw-page-title-main">Salem–Spencer set</span> Progression-free set of numbers

In mathematics, and in particular in arithmetic combinatorics, a Salem-Spencer set is a set of numbers no three of which form an arithmetic progression. Salem–Spencer sets are also called 3-AP-free sequences or progression-free sets. They have also been called non-averaging sets, but this term has also been used to denote a set of integers none of which can be obtained as the average of any subset of the other numbers. Salem-Spencer sets are named after Raphaël Salem and Donald C. Spencer, who showed in 1942 that Salem–Spencer sets can have nearly-linear size. However a later theorem of Klaus Roth shows that the size is always less than linear.

Roth's theorem on arithmetic progressions is a result in additive combinatorics concerning the existence of arithmetic progressions in subsets of the natural numbers. It was first proven by Klaus Roth in 1953. Roth's theorem is a special case of Szemerédi's theorem for the case $.$

The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators is a book on graph coloring, Ramsey theory, and the history of development of these areas, concentrating in particular on the Hadwiger–Nelson problem and on the biography of Bartel Leendert van der Waerden. It was written by Alexander Soifer and published by Springer-Verlag in 2009 (ISBN 978-0-387-74640-1).

Aaron Robertson is an American mathematician who specializes in Ramsey theory. He is a professor at Colgate University.

Hunter Snevily (1956–2013) was an American mathematician with expertise and contributions in Set theory, Graph theory, Discrete geometry, and Ramsey theory on the integers.

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 . MR 2928650.
1 2 3 4 5 6 7 8 9 10 11 Chvátal, Vašek (1970). "Some unknown van der Waerden numbers". In Guy, Richard; Hanani, Haim; Sauer, Norbert; et al. (eds.). Combinatorial Structures and Their Applications. New York: Gordon and Breach. pp. 31–33. MR 0266891.
1 2 3 4 5 6 7 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 . MR 0546646.
1 2 3 4 5 6 7 8 Kouril, Michal (2012). "Computing the van der Waerden number W(3,4)=293". Integers. 12: A46. MR 3083419.
1 2 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 . MR 0491468.
1 2 Heule, MarijnJ (2017). "Avoiding triples in arithmetic progression" (PDF). Journal of Combinatorics. 8 (3): 391–422. doi:10.4310/JOC.2017.v8.n3.a1.
1 2 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. S2CID 1696473.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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" (PDF). Geom. Funct. Anal. 11 (3): 465–588. doi:10.1007/s00039-001-0332-9. MR 1844079. S2CID 124324198.
↑ 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 . MR 0232743.
1 2 3 4 5 6 7 8 9 10 11 12 Landman, Bruce; Robertson, Aaron; Culver, Clay (2005). "Some New Exact van der Waerden Numbers" (PDF). Integers. 5 (2): A10. MR 2192088.
1 2 3 4 5 6 7 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.
1 2 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. MR 2684128. S2CID 124272560.
1 2 Ahmed, Tanbir; Kullmann, Oliver; Snevily, Hunter (2014). "On the van der Waerden numbers w(2;3,t)". Discrete Applied Mathematics . 174 (2014): 27–51. arXiv: 1102.5433 . doi: 10.1016/j.dam.2014.05.007 . MR 3215454.
1 2 3 4 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 . MR 0707027.
1 2 3 4 Ahmed, Tanbir (2012). "On computation of exact van der Waerden numbers". Integers. 12 (3): 417–425. doi:10.1515/integ.2011.112. MR 2955523. S2CID 11811448.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Ahmed, Tanbir (2013). "Some More Van der Waerden numbers". Journal of Integer Sequences. 16 (4): 13.4.4. MR 3056628.
1 2 3 4 5 6 7 8 9 10 11 Brown, T. C. (1974). "Some new van der Waerden numbers (preliminary report)". Notices of the American Mathematical Society. 21: A-432.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 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. S2CID 122129059.
↑ Schweitzer, Pascal (2009). Problems of Unknown Complexity, Graph isomorphism and Ramsey theoretic numbers (Ph.D. thesis). U. des Saarlandes.
↑ Karki, Sikij (2024). "A New van der Waerden Number" (PDF). U(t)-Mathazine (9): 34–39.
↑ 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 . JSTOR 1990952. MR 0929498.

External links

O'Bryant, Kevin & Weisstein, Eric W. "Van der Waerden Number". MathWorld .
Klarreich, Erica (2021-12-15). "Mathematician Hurls Structure and Disorder Into Century-Old Problem". Quanta Magazine .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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 . MR 2928650.

[chvatal1970-2] 1 2 3 4 5 6 7 8 9 10 11 Chvátal, Vašek (1970). "Some unknown van der Waerden numbers". In Guy, Richard; Hanani, Haim; Sauer, Norbert; et al. (eds.). Combinatorial Structures and Their Applications. New York: Gordon and Breach. pp. 31–33. MR 0266891.

[beeleroneil1979-3] 1 2 3 4 5 6 7 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 . MR 0546646.

[kouril2012-4] 1 2 3 4 5 6 7 8 Kouril, Michal (2012). "Computing the van der Waerden number W(3,4)=293". Integers. 12: A46. MR 3083419.

[ss1978-5] 1 2 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 . MR 0491468.

[heule2017-6] 1 2 Heule, MarijnJ (2017). "Avoiding triples in arithmetic progression" (PDF). Journal of Combinatorics. 8 (3): 391–422. doi:10.4310/JOC.2017.v8.n3.a1.

[kp2006-7] 1 2 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. S2CID 1696473.

[monroe2019-8] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 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" (PDF). Geom. Funct. Anal. 11 (3): 465–588. doi:10.1007/s00039-001-0332-9. MR 1844079. S2CID 124324198.

[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 . MR 0232743.

[lrc2005-11] 1 2 3 4 5 6 7 8 9 10 11 12 Landman, Bruce; Robertson, Aaron; Culver, Clay (2005). "Some New Exact van der Waerden Numbers" (PDF). Integers. 5 (2): A10. MR 2192088.

[kouril2006-12] 1 2 3 4 5 6 7 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.

[ahmed2010-13] 1 2 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. MR 2684128. S2CID 124272560.

[aks2011-14] 1 2 Ahmed, Tanbir; Kullmann, Oliver; Snevily, Hunter (2014). "On the van der Waerden numbers w(2;3,t)". Discrete Applied Mathematics . 174 (2014): 27–51. arXiv: 1102.5433 . doi: 10.1016/j.dam.2014.05.007 . MR 3215454.

[kouril2016-15] 1 2 3 4 Kouril, Michal (2015). "Leveraging FPGA clusters for SAT computations". Parallel Computing: On the Road to Exascale: 525–532.

[beeler1983-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 . MR 0707027.

[ahmed2011-17] 1 2 3 4 Ahmed, Tanbir (2012). "On computation of exact van der Waerden numbers". Integers. 12 (3): 417–425. doi:10.1515/integ.2011.112. MR 2955523. S2CID 11811448.

[ahmedJIS-18] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 Ahmed, Tanbir (2013). "Some More Van der Waerden numbers". Journal of Integer Sequences. 16 (4): 13.4.4. MR 3056628.

[brown1974-19] 1 2 3 4 5 6 7 8 9 10 11 Brown, T. C. (1974). "Some new van der Waerden numbers (preliminary report)". Notices of the American Mathematical Society. 21: A-432.

[ahmed2009-20] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 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. S2CID 122129059.

[sch2009-21] Schweitzer, Pascal (2009). Problems of Unknown Complexity, Graph isomorphism and Ramsey theoretic numbers (Ph.D. thesis). U. des Saarlandes.

[22] Karki, Sikij (2024). "A New van der Waerden Number" (PDF). U(t)-Mathazine (9): 34–39.

[23] 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 . JSTOR 1990952. MR 0929498.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

Van der Waerden number

Contents

Tables of Van der Waerden numbers

See also

Related Research Articles

References

Further reading

External links