Alexander Clifton, Ramsey Theory for Diffsequences

Van der Waerden’s theorem states that any coloring of $\mathbb{N}$ with a finite number of colors will contain arbitrarily long monochromatic arithmetic progressions. This motivates the definition of the van der Waerden number $W(r,k)$ which is the smallest $n$ such that any $r$-coloring of $\{1,2,\cdots,n\}$ guarantees the presence of a monochromatic arithmetic progression of length $k$.

It is natural to ask what other arithmetic structures exhibit van der Waerden-type results. One notion, introduced by Landman and Robertson, is that of a $D$-diffsequence, which is an increasing sequence $a_1<a_2<\cdots<a_k$ in which the consecutive differences $a_i-a_{i-1}$ all lie in some given set $D$. We say that $D$ is $r$-accessible if every $r$-coloring of $\mathbb{N}$ contains arbitrarily long monochromatic $D$-diffsequences. When $D$ is $r$-accessible, we define $\Delta(D,k;r)$ as the smallest $n$ such that any $r$-coloring of $\{1,2,\cdots,n\}$ guarantees the presence of a monochromatic $D$-diffsequence of length $k$.

One question of interest is to determine the possible behaviors of $\Delta$ as a function of $k$. In this talk, we will demonstrate that is possible for $\Delta(D,k;r)$ to grow faster than polynomial in $k$. We will also discuss a broad class of $D$’s which are not $2$-accessible.