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) = maxmax 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:
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
