Bounds on Van der Waerden Numbers and Some Related Functions

Abstract

For positive integers $s$ and $k_1,k_2,...,k_s$, let $w(k_1,k_2,...,k_s)$ be the minimum integer $n$ such that any $s$-coloring $\{1,2,...,n\}\to \{1,2,...,s\}$ admits a $k_i$-term arithmetic progression of color $i$ for some $i$, $1\le i\le s$. In the case when $k_1=k_2=...=k_s=k$ we simply write $w(k;s)$. That such a minimum integer exists follows from van der Waerden's theorem on arithmetic progressions. In the present paper we give a lower bound for $w(k,m)$ for each fixed $m$. We include a table with values of $w(k,3)$ which match this lower bound closely for $5\le k\le 16$. We also give an upper bound for $w(k,4)$, an upper bound for $w(4;s)$, and a lower bound for $w(k;s)$ for an arbitrary fixed $k$. We discuss a number of other functions that are closely related to the van der Waerden function.

13 pages