

	SAT @ Delft
Delft University of Technology	Van der Waerden numbers	ALG Group

EWI

ALG

SAT @ Delft

Van der Waerden numbers



	Home

	Publications

	Reports / theses

	March

	MiniMarch

	Awards

	Download

	Announcements

	Course slides

	Van der Waerden

	Links

Van der Waerden numbers

NEW: Visualize your own certificate.

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

preliminaries

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.

improved lower bounds

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

visualizations

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

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] 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.

Top of the page

The newest version of this page can be found at: http://www.st.ewi.tudelft.nl/sat/waerden.php
Last modified: Mon, 14 Mar 2011 09:57:56 GMT

Copyright © 2005 SAT @ Delft. Please mail if you find any errors or omissions.
All Rights Reserved. Design A. Iosup.