The van der Waerden complex

Abstract

We introduce the van der Waerden complex $\mathrm{vdW}(n,k)$ defined as the simplicial complex whose facets correspond to arithmetic progressions of length $k$ in the vertex set $\{1,2,\dots ,n\}$. We show the van der Waerden complex $\mathrm{vdW}(n,k)$ is homotopy equivalent to a $CW$-complex whose cells asymptotically have dimension at most $\log k/\log \log k$. Furthermore, we give bounds on $n$ and $k$ which imply that the van der Waerden complex is contractible.