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