Journal of Combinatorics
Volume 8 (2017)
Guest Editor: Steve Butler (Iowa State University)
Avoiding triples in arithmetic progression
Pages: 391 – 422
Some patterns cannot be avoided ad infinitum. A well-known example of such a pattern is an arithmetic progression in partitions of natural numbers. We observed that in order to avoid arithmetic progressions, other patterns emerge. A visualization is presented that reveals these patterns. We capitalize on the observed patterns by constructing techniques to avoid arithmetic progressions.
More formally, van der Waerden numbers $W(k, l)$ express the smallest $n$ such that partitioning $\lbrace 1, \dotsc , n \rbrace$ into $k$ sets yields at least one set containing an arithmetic progression of length at least $l$. Computing these numbers for $l \gt 2$ is a very hard combinatorial problem. We focus on avoiding triples $(l = 3)$ in arithmetic progressions. We guide the search procedure by transforming observed symmetries in best known lower bounds into additional constraints. Using our method, several lower bounds for van der Waerden numbers have been improved. As a consequence, a new pattern also emerges between the best known lower bounds. We conclude with open problems regarding van der Waerden numbers as well as some bold conjectures that challenges existing work on the subject.
van der Waerden numbers, SAT, symmetries
2010 Mathematics Subject Classification
Primary 05D10. Secondary 68R05.
This work is supported by the NSF under grant number CCF-1526760.
Paper received on 17 May 2017.