Erdős–Szekeres theorem for cyclic permutations
Copyright policy )Erdős–Szekeres theorem for cyclic permutations
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
- University of South Carolina United States
- University of Johannesburg South Africa
- University of South Carolina System United States
Permutations, words, matrices, cyclic Erdős-Szekeres theorem, FOS: Mathematics, Combinatorics (math.CO), 05D99, 05D10, cyclic Erdős–Szekeres theorem
Permutations, words, matrices, cyclic Erdős-Szekeres theorem, FOS: Mathematics, Combinatorics (math.CO), 05D99, 05D10, cyclic Erdős–Szekeres theorem
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).6 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!