## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  656.05002
Autor:  Erdös, Paul; Linial, N.; Moran, S.
Title:  Extremal problems on permutations under cyclic equivalence. (In English)
Source:  Discrete Math. 64, 1-11 (1987).
Review:  Let \sigma in Sn be a permutation and let [\sigma] be the class of all cyclic permutations of \sigma. For \pi in Sn, \pi = (b1,b2,...,bn), denote by \piR the permutation (bn,...,b1) in Sn. Also denote by < \sigma > the set [\sigma]\cup {\tauR;   \tau in [\sigma]}. In this paper the authors study the function F(n) = max max I(\sigma), where I(\sigma) is the number of inversions in \sigma, the max is over \pi in Sn and the min over \sigma in [\pi].
The main result is the following theorem:

0.304^-n2+0(n) = \frac{8-\pi}{16}· n2- 3n/2 \leq F(n) \leq \frac{n2}{3}-\frac{3n-1}{6} = 0.333^+n2+0(n).

The measures of complexity considered are the number of inversions and the diameter of the permutation.
Reviewer:  E.Fuchs
Classif.:  * 05A05 Combinatorial choice problems
Keywords:  permutations; inversions

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag