A Note on a Ramsey-Type Problem for Sequences

Abstract

Two sequences $\{x_i\}_{i=1}^{t}$ and $\{y_i\}_{i=1}^t$ of distinct integers are similar if their entries are order-isomorphic. Let $f(r,X)$ be the length of the shortest sequence $Y$ such that any $r$-coloring of the entries of $Y$ yields a monochromatic subsequence that is also similar to $X$. In this note we show that for any fixed non-monotone sequence $X$, $f(r,X)=\Theta(r^2)$, otherwise, for a monotone $X$, $f(r,X)=\Theta(r)$.