Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive

Abstract

The van der Waerden number $W(k,2)$ is the smallest integer $n$ such that every $2$-coloring of 1 to $n$ has a monochromatic arithmetic progression of length $k$. The existence of such an $n$ for any $k$ is due to van der Waerden but known upper bounds on $W(k,2)$ are enormous. Much effort was put into developing lower bounds on $W(k,2)$. Most of these lower bound proofs employ the probabilistic method often in combination with the Lovász Local Lemma. While these proofs show the existence of a $2$-coloring that has no monochromatic arithmetic progression of length $k$ they provide no efficient algorithm to find such a coloring. These kind of proofs are often informally called nonconstructive in contrast to constructive proofs that provide an efficient algorithm.

This paper clarifies these notions and gives definitions for deterministic- and randomized-constructive proofs as different types of constructive proofs. We then survey the literature on lower bounds on $W(k,2)$ in this light. We show how known nonconstructive lower bound proofs based on the Lovász Local Lemma can be made randomized-constructive using the recent algorithms of Moser and Tardos. We also use a derandomization of Chandrasekaran, Goyal and Haeupler to transform these proofs into deterministic-constructive proofs. We provide greatly simplified and fully self-contained proofs and descriptions for these algorithms.