Erdős-Szekeres theorem for cyclic permutations
By Zhiyu Wang
29 March 2019
We provide a cyclic permutation analogue of the Erdős-Szekeres theorem. In particular, we show that every cyclic permutation of length (k-1)(l-1)+2 has either an increasing cyclic sub-permutation of length k+1 or a decreasing cyclic sub-permutation of length l+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 l+1. Joint work with Eva Czabarka.