Journal article 1305 views
On the van der Waerden numbers
Tanbir Ahmed,
Oliver Kullmann 
,
Hunter Snevily
,
Hunter Snevily
Discrete Applied Mathematics, Volume: 174, Pages: 27 - 51
Swansea University Author:
Oliver Kullmann
Full text not available from this repository: check for access using links below.
DOI (Published version): 10.1016/j.dam.2014.05.007
Abstract
We present results and conjectures on the van der Waerden numbers w(2;3,t). and on the new palindromic van der Waerden numbers pdw(2;3,t). We have computed the new number w(2;3,19) = 349, and we provide lower bounds for 20 <= t <= 39, where for t <= 30 we conjecture these lower bounds to be...
| Published in: | Discrete Applied Mathematics |
|---|---|
| Published: |
2014
|
| Online Access: |
http://www.cs.swan.ac.uk/~csoliver/papers.html#VDW232011 |
| URI: | https://cronfa.swan.ac.uk/Record/cronfa18005 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Abstract: |
We present results and conjectures on the van der Waerden numbers w(2;3,t). and on the new palindromic van der Waerden numbers pdw(2;3,t). We have computed the new number w(2;3,19) = 349, and we provide lower bounds for 20 <= t <= 39, where for t <= 30 we conjecture these lower bounds to be exact. The lower bounds for 24 <= t <= 30 refute the conjecture that w(2;3,t) <= t^2, and we present an improved conjecture. We also investigate regularities in the good partitions (certificates) to better understand the lower bounds. Motivated by such regularities, we introduce *palindromic van der Waerden numbers* pdw(k; t_0,...,t_{k-1}), defined as ordinary van der Waerden numbers w(k; t_0,...,t_{k-1}), however only allowing palindromic solutions (good partitions), defined as reading the same from both ends. We compute pdw(2;3,t) for 3 <= t <= 27, and we provide lower bounds, which we conjecture to be exact, for t <= 35. All computations are based on SAT solving, and we discuss the various relations between SAT solving and Ramsey theory. Especially we introduce a novel (open-source) SAT solver, the tawSolver , which performs best on the SAT instances studied here, and which is actually the original DLL-solver, but with an efficient implementation and a modern heuristic typical for look-ahead solvers (applying the theory developed in the SAT handbook article ). |
|---|---|
| Keywords: |
SAT solving, Ramsey numbers, van der Waerden numbers, distributed computing |
| College: |
Faculty of Science and Engineering |
| Start Page: |
27 |
| End Page: |
51 |