Arrangements and Ranking Patterns

Hidehiko Kamiya^{1}, Peter Orlik^{2}, Akimichi Takemura^{3}, and Hiroaki Terao^{4}

kamiya@e.okayama-u.ac.jp

orlik@math.wisc.edu

takemura@stat.t.u-tokyo.ac.jp

hterao@comp.metro-u.ac.jp

Annals of Combinatorics 10 (2) p. 219-235 June, 2006

Abstract:

In the unidimensional unfolding model, given m objects in general position on the real line, there arise 1+m(m - 1)/2 rankings. The set of rankings is called the ranking pattern of the m given objects. Change of the position of these m objects results in change of the ranking pattern. In this paper we use arrangement theory to determine the number of ranking patterns theoretically for all m and numerically for m ¡Ü 8. We also consider the probability of the occurrence of each ranking pattern when the objects are randomly chosen.

References:

1. C.A. Athanasiadis, Generalized Catalan numbers, Weyl groups and arrangements of hyperplanes, Bull. London Math. Soc. 36 (2004) 294–302.

2. N. Bourbaki, Groupes et Algèbres de Lie, Ch. 4-6, Hermann, Paris, 1968.

3. C.H. Coombs, Psychological scaling without a unit of measurement, Psychol. Rev. 57 (1950) 145–158.

4. C.H. Coombs, A theory of psychological scaling, Engng. Res. Inst. Bull. No. 34, University of Michigan Press, Ann Arbor, 1952.

5. C.H. Coombs, A Theory of Data, John Wiley & Sons, New York, 1964.

6. H. Crapo and G.-C. Rota, On the Foundations of Combinatorial Theory: Combinatorial Geometries, MIT Press, Cambridge, MA, 1970.

7. B.C. Eaton and R.G. Lipsey, The principle of minimum differentiation reconsidered: some new developments in the theory of spatial competition, Rev. Econom. Stud. 42 (1975) 27–49.

8. B.C. Eaton and R.G. Lipsey, The non-uniqueness of equilibrium in the Löschan location model, Amer. Econ. Rev. 66 (1976) 77–93.

9. H. Hotelling, Stability in competition, Econom. J. 39 (1929) 41–57.

10. H. Kamiya and A. Takemura, On rankings generated by pairwise linear discriminant analysis of m populations, J. Multivariate Anal. 61 (1997) 1–28.

11. J.I. Marden, Analyzing and Modeling Rank Data, Chapman & Hall, London, 1995.

12. R.J. Muirhead, Aspects of Multivariate Statistical Theory, John Wiley & Sons, New York, 1982.

13. A. Okabe, B. Boots, K. Sugihara, and S.N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, 2nd Ed., John Wiley & Sons, Chichester, 2000.

14. P. Orlik and H. Terao, Arrangements of Hyperplanes, Grundlehren Math. Wiss. Vol 300, Springer-Verlag, Berlin, 1992.

15. L. Schläfli, On the multiple integral ∫^{n}*dxdy…dz* whose limits are p_{1} = a_{1}x+b_{1}y+¡+
h_{1}z > 0, p_{2} > 0,¡ , p_{n} > 0, and x^{2} +y^{2} +¡+z^{2} < 1, Q. J. Math. 2 (1858) 269–300.
Continued in 3 (1860) 54–68, 97–108.

16. R. Stanley, Ordering events in Minkowski space, Adv. in Appl. Math., to appear.

17. H. Terao, The Jacobians and the discriminants of finite reflection groups, Tohoku Math. J. (2) 41 (1989) 237–247.

18. H. Terao, Moduli space of combinatorially equivalent arrangements of hyperplanes and logarithmic Gauss-Manin connections, Topology Appl. 118 (2002) 255–274.

19. R.M. Thrall, A combinatorial problem, Michigan Math. J. 1 (1952) 81–88.

20. T. Zaslavsky, Facing up to Arrangements: Face-Count Formulas for Partitions of Space by Hyperplanes, Vol. 1, Mem. Amer. Math. Soc., Providence, 1975.