A New Lower Bound for van der Waerden Numbers

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\le k$ then $w(r,k)>p\cdot \left(w\left(r-\lceil \frac{r}{p}\rceil ,k\right)-1\right)$. This recurrence gives the lower bound $w(r,p+1)>p^{r-1}{2}^p$ when $r\le 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.

9 pages, 1 table. Article has been accepted into the European Journal of Combinatorics

References in corpus (2)

• A quantitative improvement for Roth's theorem on arithmetic progressions
• New Lower Bounds for van der Waerden Numbers Using Distributed Computing

Cited by in corpus (2)

• New Lower Bounds for van der Waerden Numbers Using Distributed Computing
• A Constructive Lower Bound on Szemerédi's Theorem