On Integer Sets Excluding Permutation Pattern Waves

Abstract

We study Ramsey-type problems on sets avoiding sequences whose consecutive differences have a fixed relative order. For a given permutation $\pi \in S_k$, a $\pi$-wave is a sequence $x_1<\cdots <x_{k+1}$ such that $x_{i+1}-x_i>x_{j+1}-x_j$ if and only if $\pi (i)>\pi (j)$. A subset of $[n]=\{1,\dots ,n\}$ is $\pi$-wave-free if it does not contain any $\pi$-wave. Our first main result shows that the size of the largest $\pi$-wave-free subset of $[n]$ is $O\left((\log n{)}^{k-1}\right)$. We then classify all permutations for which this bound is tight. In the cases where it is not tight, we prove stronger polylogarithmic upper bounds. We then apply these bounds to a closely related coloring problem studied by Landman and Robertson.

14 pages