No Cover Image

Journal article 1473 views

On the van der Waerden numbers

Tanbir Ahmed, Oliver Kullmann Orcid Logo, Hunter Snevily

Discrete Applied Mathematics, Volume: 174, Pages: 27 - 51

Swansea University Author: Oliver Kullmann Orcid Logo

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

Full description

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!
first_indexed 2014-05-29T10:24:51Z
last_indexed 2023-01-31T03:23:35Z
id cronfa18005
recordtype SURis
fullrecord <?xml version="1.0"?><rfc1807><datestamp>2023-01-30T14:46:34.8374722</datestamp><bib-version>v2</bib-version><id>18005</id><entry>2014-05-27</entry><title>On the van der Waerden numbers</title><swanseaauthors><author><sid>2b410f26f9324d6b06c2b98f67362d05</sid><ORCID>0000-0003-3021-0095</ORCID><firstname>Oliver</firstname><surname>Kullmann</surname><name>Oliver Kullmann</name><active>true</active><ethesisStudent>false</ethesisStudent></author></swanseaauthors><date>2014-05-27</date><deptcode>SCS</deptcode><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 &lt;= t &lt;= 39, where for t &lt;= 30 we conjecture these lower bounds to be exact. The lower bounds for 24 &lt;= t &lt;= 30 refute the conjecture that w(2;3,t) &lt;= 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 &lt;= t &lt;= 27, and we provide lower bounds, which we conjecture to be exact, for t &lt;= 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 ).</abstract><type>Journal Article</type><journal>Discrete Applied Mathematics</journal><volume>174</volume><journalNumber/><paginationStart>27</paginationStart><paginationEnd>51</paginationEnd><publisher/><placeOfPublication/><isbnPrint/><isbnElectronic/><issnPrint/><issnElectronic/><keywords>SAT solving, Ramsey numbers, van der Waerden numbers, distributed computing</keywords><publishedDay>10</publishedDay><publishedMonth>9</publishedMonth><publishedYear>2014</publishedYear><publishedDate>2014-09-10</publishedDate><doi>10.1016/j.dam.2014.05.007</doi><url>http://www.cs.swan.ac.uk/~csoliver/papers.html#VDW232011</url><notes/><college>COLLEGE NANME</college><department>Computer Science</department><CollegeCode>COLLEGE CODE</CollegeCode><DepartmentCode>SCS</DepartmentCode><institution>Swansea University</institution><apcterm/><funders/><projectreference/><lastEdited>2023-01-30T14:46:34.8374722</lastEdited><Created>2014-05-27T06:48:58.3101803</Created><path><level id="1">Faculty of Science and Engineering</level><level id="2">School of Mathematics and Computer Science - Computer Science</level></path><authors><author><firstname>Tanbir</firstname><surname>Ahmed</surname><order>1</order></author><author><firstname>Oliver</firstname><surname>Kullmann</surname><orcid>0000-0003-3021-0095</orcid><order>2</order></author><author><firstname>Hunter</firstname><surname>Snevily</surname><order>3</order></author></authors><documents/><OutputDurs/></rfc1807>
spelling 2023-01-30T14:46:34.8374722 v2 18005 2014-05-27 On the van der Waerden numbers 2b410f26f9324d6b06c2b98f67362d05 0000-0003-3021-0095 Oliver Kullmann Oliver Kullmann true false 2014-05-27 SCS 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 ). Journal Article Discrete Applied Mathematics 174 27 51 SAT solving, Ramsey numbers, van der Waerden numbers, distributed computing 10 9 2014 2014-09-10 10.1016/j.dam.2014.05.007 http://www.cs.swan.ac.uk/~csoliver/papers.html#VDW232011 COLLEGE NANME Computer Science COLLEGE CODE SCS Swansea University 2023-01-30T14:46:34.8374722 2014-05-27T06:48:58.3101803 Faculty of Science and Engineering School of Mathematics and Computer Science - Computer Science Tanbir Ahmed 1 Oliver Kullmann 0000-0003-3021-0095 2 Hunter Snevily 3
title On the van der Waerden numbers
spellingShingle On the van der Waerden numbers
Oliver Kullmann
title_short On the van der Waerden numbers
title_full On the van der Waerden numbers
title_fullStr On the van der Waerden numbers
title_full_unstemmed On the van der Waerden numbers
title_sort On the van der Waerden numbers
author_id_str_mv 2b410f26f9324d6b06c2b98f67362d05
author_id_fullname_str_mv 2b410f26f9324d6b06c2b98f67362d05_***_Oliver Kullmann
author Oliver Kullmann
author2 Tanbir Ahmed
Oliver Kullmann
Hunter Snevily
format Journal article
container_title Discrete Applied Mathematics
container_volume 174
container_start_page 27
publishDate 2014
institution Swansea University
doi_str_mv 10.1016/j.dam.2014.05.007
college_str Faculty of Science and Engineering
hierarchytype
hierarchy_top_id facultyofscienceandengineering
hierarchy_top_title Faculty of Science and Engineering
hierarchy_parent_id facultyofscienceandengineering
hierarchy_parent_title Faculty of Science and Engineering
department_str School of Mathematics and Computer Science - Computer Science{{{_:::_}}}Faculty of Science and Engineering{{{_:::_}}}School of Mathematics and Computer Science - Computer Science
url http://www.cs.swan.ac.uk/~csoliver/papers.html#VDW232011
document_store_str 0
active_str 0
description 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 ).
published_date 2014-09-10T03:20:59Z
_version_ 1763750612597473280
score 11.035634

Similar Items