Extremal problems on permutations under cyclic equivalence

✍ Scribed by P Erdös; N Linial; S Moran

• Publisher: Elsevier Science
• Year: 1987
• Tongue: English
• Weight: 608 KB
• Volume: 64
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(87)90235-4

✦ Synopsis

How much can a permutation be simplified by means of cyclic rotations? For functions f: S,.-o Z which give a measure of complexity to permutations we are interested in finding

where the max is over o e S,, and the min is over u which are cyclically equivalent to o.

The measures of complexity considered are the number of inversions and the diameter of the permutation. The effect of allowing a reflection as well as rotations is also considered.