TU Delft Algorithmics
SAT @ Delft
Delft University of Technology Van der Waerden numbers ALG Group
EWI ALG SAT @ DelftVan der Waerden numbers
eng
 
 
 
 
 
 
 
 
 
 
 

Van der Waerden numbers


NEW: Visualize your own certificate.

For the latest description of our method see Improving the odds.

r \ k 3 4 5 6 7 8 9
2 9 35 178 1132[3] > 3703[4] > 7484[4] >27113[4]
3 27 > 292[4] > 1209[?] > 8886[4] > 43855[4] >238400[4*]  
4 76 > 1048[4] > 10437[4] > 90306[4] >387967[4*]    
5 >125[1] >2254[4] >24045[4] >246956[4*]      
6 >207[4] >9778[4] >56693[4*] >600486[4*]      
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 1132 > 3703 > 11495 > 41265
3 27 > 292 > 2173 > 11191 > 48811 > 238400  
4 76 > 1048 > 17705 > 91331 > 420217    
5 > 170 > 2254 > 98740 > 540025      
6 > 223 > 9778 > 98748 > 816981      
Table 2: Improved best known lower bounds to Van der Waerden numbers
Of all best known lower bounds there exists a certificate that has some symmetric properties. To show these symmetries one can use the visualization technique described in [2]: When r-partitioning is involved we use r directions in the plane, where the angle between two consecutive directions is 360 / r . Starting from the beginning of the certicate a line segment is drawn in the direction associated with the subset containing number 1. From the endpoint of that line segment a line segment with equal length is drawn in the direction associated with the subset containing number 2. This process is repeated up to number n of the certicate. The line segments are gradually colored from red to blue to green and back to red. This visualization is only applicable for r > 2.

r \ k 3 4 5 6
3

W(3,3) > 26


W(3,4) > 292


W(3,5) > 2173


W(3,6) > 11191
4

W(4,3) > 75


W(4,4) > 1048


W(4,5) > 17705


W(4,6) > 91331
5

W(5,3) > 170


W(5,4) > 2254


W(5,5) > 98740


W(5,6) > 540025
Table 3: Visualisations of a certificate of the best known lower bounds to Van der Waerden numbers

[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] P. Herwig, M.J.H. Heule, M. van Lambalgen, and H. van Maaren. A new method to construct lower bounds for Van der Waerden numbers. The Electronic Journal of Combinatorics 14 (2007) #R6. [ .pdf ]

[3] M. Kouril and J.L. Paul. The Van der Waerden Number W(2,6) is 1132. Experimental Mathematics (to appear).

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