A new lower bound for van der Waerden numbers. (March 2018) - Blankenship, Thomas; Cummings, Jay; Taranchuk, Vladislav
Abstract: In this paper we prove a new recurrence relation on the van der Waerden numbers, w ( r, k ) . In particular, if p is a prime and p ≤ k then w ( r, k ) > p ⋅ w r − r p, k − 1 . This recurrence gives the lower bound w ( r, p + 1 ) > p r − 1 2 p when r ≤ p, which generalizes Berlekamp's theorem on 2-colorings, and gives the best known bound for a large interval of r . The recurrence can also be used to construct explicit valid colorings, and it improves known lower bounds on small van der Waerden numbers.