A note on a Ramsey-type problem for sequences (Q743660)

Summary: 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)\).