Annals of Combinatorics 10 (2006) 219-235
Arrangements and Ranking Patterns
Hidehiko Kamiya, Peter Orlik, Akimichi Takemura, and Hiroaki Terao
Faculty of Economics, Okayama University, Okayama 700-8530, Japan
kamiya@e.okayama-u.ac.jp
Department of Mathematics, University of Wisconsin, Madison, WI 53706, USA
orlik@math.wisc.edu
Graduate School of Information Science and Technology, University of Tokyo, Tokyo 113-0033,
Japan
takemura@stat.t.u-tokyo.ac.jp
Department of Mathematics, Hokkaido University, Sapporo 060-0810, Japan
hterao@comp.metro-u.ac.jp
Received March 5, 2005
AMS Subject Classification: 32S22, 52C35, 62F07
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.
Keywords: Phylogenetic tree, Semilabelled, X-tree, Graph metric, Parity split
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 
whose limits are p1 = a1x+b1y+···+
h1z > 0, p2 > 0, ··· , pn > 0, and x2 +y2 +···+z2 < 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.