\documentclass[12pt]{article}
\usepackage{amsmath,mathrsfs,bbm}
\usepackage{amssymb}
\textwidth=4.825in
\overfullrule=0pt
\thispagestyle{empty}
\begin{document}
\noindent
%
%
{\bf William Gasarch and Bernhard Haeupler}
%
%
\medskip
\noindent
%
%
{\bf Lower Bounds on van der Waerden Numbers: Randomized- and Deterministic-Constructive}
%
%
\vskip 5mm
\noindent
%
%
%
%
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{\'a}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 {\it nonconstructive} in contrast to {\it
constructive} proofs that provide an efficient algorithm.
This paper clarifies these notions and gives definitions for
deter\-ministic- 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{\'a}sz Local Lemma can be made
ran\-domized-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.
\end{document}