On the van der Waerden numbers w(2; 3, t)
From MaRDI portal
Publication:400514
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 reglarities, 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. Different from the situation for ordinary van der Waerden numbers, these "numbers" need actually to be pairs of numbers. 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 of the second author).
Recommendations
Cites work
- scientific article; zbMATH DE number 5613972 (Why is no real title available?)
- scientific article; zbMATH DE number 5014484 (Why is no real title available?)
- scientific article; zbMATH DE number 5510691 (Why is no real title available?)
- scientific article; zbMATH DE number 5510692 (Why is no real title available?)
- scientific article; zbMATH DE number 5620835 (Why is no real title available?)
- scientific article; zbMATH DE number 3523693 (Why is no real title available?)
- scientific article; zbMATH DE number 5493266 (Why is no real title available?)
- scientific article; zbMATH DE number 3385632 (Why is no real title available?)
- A machine program for theorem-proving
- A new method to construct lower bounds for van der Waerden numbers
- A parallelization scheme based on work stealing for a class of SAT solvers
- Bounds on some van der Waerden numbers
- Branching rules for satisfiability
- Computing the van der Waerden number \(W(3,4)=293\)
- Generalising and unifying SLUR and unit-refutation completeness
- Generalising unit-refutation completeness and SLUR via nested input resolution
- Green-Tao Numbers and SAT
- Incorporating clause learning in grid-based randomized SAT solving
- Model counting: a new stategy for obtaining good bounds
- On computation of exact van der Waerden numbers
- On the van der Waerden numbers \(\mathrm{w}(2; 3, t)\)
- PSATO: A distributed propositional prover and its application to quasigroup problems
- Partitioning SAT instances for distributed solving
- Ramsey theory applications
- Satisfiability and computing van der Waerden numbers
- Small Ramsey numbers
- Software verification for weak memory via program transformation
- Some Progression-Free Partitions Constructed using Folkman's Method
- Some more van der Waerden numbers
- Some new van der Waerden numbers
- Some new van der Waerden numbers and some van der Waerden-type numbers
- The Multi-SAT algorithm
- The van der Waerden NumberW(2, 6) Is 1132
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- Theory and Applications of Satisfiability Testing
- Theory and applications of satisfiability testing -- SAT 2010. 13th international conference, SAT 2010, Edinburgh, UK, July 11--14, 2010. Proceedings
- Theory and applications of satisfiability testing. 7th international conference, SAT 2004, Vancouver, BC, Canada, May 10--13, 2004. Revised selected papers.
- Top-down algorithms for constructing structured DNNF: theoretical and practical implications
- Tutorial on Model Checking: Modelling and Verification in Computer Science
- Two new van der Waerden numbers: \(w(2;3,17)\) and \(w(2;3,18)\)
- Two techniques for minimizing resolution proofs
Cited in
(14)- On the van der Waerden numbers \(\mathrm{w}(2; 3, t)\)
- Projection heuristics for binary branchings between sum and product
- Theory and Applications of Satisfiability Testing
- A novel SAT solver for the van der Waerden numbers
- Solving and Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer
- scientific article; zbMATH DE number 1545450 (Why is no real title available?)
- Satisfiability and computing van der Waerden numbers
- Theory and Applications of Satisfiability Testing
- Some results on a class of mixed van der Waerden numbers
- Computing the van der Waerden number \(W(3,4)=293\)
- A note on the mixed van der Waerden number
- A nonexistence certificate for projective planes of order ten with weight 15 codewords
- The SAT+CAS method for combinatorial search with applications to best matrices
- New lower bounds for van der Waerden numbers
Describes a project that uses
Uses Software
This page was built for publication: On the van der Waerden numbers \(\mathrm{w}(2; 3, t)\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q400514)
