Article ID Journal Published Year Pages File Type
8903630 European Journal of Combinatorics 2018 6 Pages PDF
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⋅wr−rp,k−1. This recurrence gives the lower bound w(r,p+1)>pr−12p 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.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,