On September 27, 2022, Alexander Clifton from the IBS Discrete Mathematics Group gave a talk on the existence of a monochromatic increasing sequence with all gaps in a fixed set in any coloring of the set of positive integers at the Discrete Math Seminar. The title of his talk was “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.
The IBS discrete mathematics group welcomes Dr. Alexander Clifton, a new research fellow at the IBS discrete mathematics group from August 16, 2022. He received his Ph.D. from Emory University under the supervision of Prof. Hao Huang. He is interested in extremal combinatorics.
