A classical theorem, due to van der Waerden, states that for every positive integers k and l, there is a positive integer m such that every partition of [m] into k blocks has a block containing an arithmetic progression of length l. The least such number is denoted W(k,l). The only five non-trivial numbers are shown below.
 
 

1. Critical configurations for [75]:
In this research we used SAT solvers to compute all counterexamples to W(4,3)=75 (up to symmetries: permutation of blocks and the flip operation on partitions, that is, a permutation of partitions induced by the following permutation of [75]: f(x) = 76 -x).
We found 30 such counterexamples or critical configurations for 75.

2. Lower bounds on van der Waerden numbers found by SAT solvers:
We also used our program WSAT(CC), a local-search solver for the logic of propositional schemata   extended with cardinality constraints (logic PS+) to compute lower bounds on some van der Waerden numbers [2][3]. For each pair (k,l) of parameters, to show that W(k,l)> m, we found a partition of [m] into k blocks so that no block contains an arithmetic progression of length l. The lower bounds are in the table below (for more details, please check out the info page). Each entry provides a link to an appropriate counterexample partition.
 
 

3. Best known lower bounds on van der Waerden numbers (as of 9/10/2004):
Many researchers have been working on this problem. The following table shows the current best known lower bounds on some van der Waerden numbers. Please refer to the references for more information. Our method contributed one lower bound in the table, namely the lower bound for W(5,3).
 
 

Reference

[1] Satisfiability and Computing van der Waerden numbers
M.R. Dransfield, L. Liu, V. Marek, M. Truszczynski. The Electronic Journal of Combinatorics, vol. 11(1), 2004.

[2] Local search with bootstrapping
L. Liu and M. Truszczynski. Proceedings of SAT-2004.

[3] Local-search techniques for propositional logic with cardinality constraints
L. Liu and M. Truszczynski. Proceedings of CP-2003.

[4] Progressions in Every Two-coloration of Z_n
H. Y. Song, H. Taylor and S. W. Golomb. Journal of Combinatorial Theory, Series A, vol. 61, no. 2, pp. 211-221, Nov. 1992

[5] van der Waerden numbers
Mark Cooke

[6] Ramsey Theory on the Integers (Student Mathematical Library, V. 24)
Bruce M. Landman, Aaron Robertson. American Mathematical Society. January 9, 2004

[7] Lower Bounds for Van der Waerden Numbers
Geoffrey Exoo

Activities discussed on this page are partially supported by the National Science Foundation. Any opinions, findings, and conclusions or recommendations expressed here  are those of the author(s) and do not necessarily reflect the views of the National Science Foundation

Last modified: September 10, 2004