new lower bounds to Van der Waerden numbers


MSc students

Anne-Aimée Bun
Paul Herwig
Martijn van Lambalgen
Michel Meulpolder

supervisors

Marijn Heule
Hans van Maaren




preliminary results

Last decade only two improved lower bounds to Van der Waerden were found [1,2]. Using a combination of symmetry reasoning, satisfiability solving and number theory, seven new lower bounds were established. Our preliminary results are presented in table 2.


r \ k 3 4 5 6 7 8 9
2 9 35 178 > 1131[2] > 3703[3] > 7484[3] >27113[3]
3 27 > 292[3] > 1209[?] > 8886[3] > 43855[3] >238400[3*]  
4 76 > 1048[3] > 10437[3] > 90306[3] >387967[3*]    
5 >125[1] >2254[3] >24045[3] >246956[3*]      
6 >207[3] >9778[3] >56693[3*] >100566[3*]      

Table 1: Current best known lower bounds to Van der Waerden numbers


* This lower bound can be constructed using the method described in the paper, but due to lack of computational power these results are not mentioned.


r \ k
 3 4 5 6 7 8 9
2 9 35 178 > 1131 > 3703 > 11495 > 41265
3 27 > 292 > 1209 > 8886 > 43855 > 238400  
4 76 > 1048 > 17705 > 91331 > 393469    
5 > 125 > 2254 > 24045 > 246956      
6 > 207 > 9778 > 63473 > 432071      

Table 2: Updated best known lower bounds to Van der Waerden numbers




references

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

[2] M. Kouril and J. Franco. Resolution Tunnes for Improved SAT Solver Performance. Lecture Notes in Computer Science 3569 (2005) 143-157.

[3] J.R. Rabung. Some Prgrogression-free Partitions Constructed Using Folkman's Method. Canadian Mathematical Bulletin, vol. 22 (1979) 87-91.