Progressions and Paths in Colorings of $\mathbb{Z}$

Abstract

A $\text{ladder}$ is a set $S\subseteq {\mathbb{Z}}^{+}$ such that any finite coloring of $\mathbb{Z}$ contains arbitrarily long monochromatic progressions with common difference in $S$. Van der Waerden's theorem famously asserts that ${\mathbb{Z}}^{+}$ itself is a ladder. We also discuss variants of ladders, namely $\text{accessible}$ and $\text{walkable}$ sets, which are sets $S$ such that any coloring of $\mathbb{Z}$ contains arbitrarily long (for accessible sets) or infinite (for walkable sets) monochromatic sequences with consecutive differences in $S$. We show that sets with upper density 1 are ladders and walkable. We also show that all directed graphs with infinite chromatic number are accessible, and reduce the bound on the walkability order of sparse sets from 3 to 2, making it tight.

7 pages