A new lower bound for van der Waerden numbers. (March 2018)

• Record Type: Journal Article
• Authors: Blankenship, Thomas; Cummings, Jay; Taranchuk, Vladislav
• Is Part Of: European journal of combinatorics. Volume 69(2018)
• Page Start: 163
• Page End: 168
• Publication Date: 2018-03
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2017.10.007
• Languages: English
• ISSNs: 0195-6698

Abstract

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.