Erdős-Szekeres theorem for cyclic permutations

Abstract

We provide a cyclic permutation analogue of the Erd\H os-Szekeres theorem. In particular, we show that every cyclic permutation of length $(k-1)(\ell -1)+2$ has either an increasing cyclic sub-permutation of length $k+1$ or a decreasing cyclic sub-permutation of length $\ell +1$, and show that the result is tight. We also characterize all maximum-length cyclic permutations that do not have an increasing cyclic sub-permutation of length $k+1$ or a decreasing cyclic sub-permutation of length $\ell +1$.

8 pages, 2 figures