## Erdős-Szekeres theorem for cyclic permutations.(English)Zbl 1400.05011

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

### MSC:

 05A05 Permutations, words, matrices

### Keywords:

cyclic Erdős-Szekeres theorem
Full Text:

### References:

 [1] 10.1016/j.ipl.2006.08.003 · Zbl 1185.68840 [2] 10.1093/nar/27.11.2369 [3] ; Erdős, Compositio Math., 2, 463 (1935) [4] 10.4153/cjm-1954-030-1 · Zbl 0055.25404 [5] 10.1016/j.aam.2005.08.008 · Zbl 1109.05015 [6] 10.1017/CBO9780511609589
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.