JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 23, No 2 (2006)

Antoine Deza¹ , Boris Goldengorin² and Dmitrii V. Pasechnik³

¹McMaster University Dept. of Computing and Software Hamilton Ontario Canada L8S 4K1 Hamilton Ontario Canada L8S 4K1
²University of Groningen Dept. of Econometrics and Operations Research P.O. Box 800 9700 AV Groningen The Netherlands P.O. Box 800 9700 AV Groningen The Netherlands
³Nanyang Technological University School of Physical and Mathematical Sciences 50 Nanyang Avenue Singapore 639798 50 Nanyang Avenue Singapore 639798

We show that the symmetry groups of the cut cone Cut _n and the metric cone Met _n both consist of the isometries induced by the permutations on {1,..., n} \{1,\dots,n\} , that is, Is( Cut n)= Is( Met n) @ Sym n Is(\mathrm{Cut}{n})=Is(\mathrm{Met}{n})\simeq Sym{n} for n \geq  5. For n = 4 we have Is( Cut4)= Is( Met4) @ Sym3\times  Sym4 Is(\mathrm{Cut}{4})=Is(\mathrm{Met}{4})\simeq Sym{3}\times Sym{4} . This result can be extended to cones containing the cuts as extreme rays and for which the triangle inequalities are facet-inducing. For instance, Is ( Hyp _n) @ Sym( n) Is ({\rm Hyp}_n) \simeq Sym(n) for n \geq  5, where Hyp _n denotes the hypermetric cone.

1. P. Assouad and M. Deza, Metric subspaces of l1. Publications mathématiques d'orsay 82-03, Université de Paris Sud, Orsay, 1982.
2. A.E. Brouwer, A.M. Cohen, and A. Neumaier, Distance-Regular Graphs, Springer-Verlag, Berlin- Heidelberg-New York, 1989.
3. P.J. Cameron, Permutation Groups, volume 45 of London Mathematical Society Student Texts, Cambridge University Press, Cambridge, 1999.
4. A. Deza and M. Deza, “On the skeleton of the dual cut polytope,” in Jerusalem combinatorics '93, volume 178 of Contemp. Math., Amer. Math. Soc., Providence, RI, 1994 pp. 101-111.
5. A. Deza and M. Deza, “The ridge graph of the metric polytope and some relatives,” in Polytopes: Abstract, convex and computational (Scarborough, ON, 1993), volume 440 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., pp. 359-372. Kluwer Acad. Publ., Dordrecht, 1994.
6. A. Deza, M. Deza, and K. Fukuda, “On skeletons, diameters and volumes of metric polyhedra,” in Combinatorics and Computer Science (Brest, 1995), volume 1120 of Lecture Notes in Comput. Sci., pp. 112-128. Springer, Berlin, 1996.
7. M. Deza and M. Dutour, “Data mining for cones of metrics, quasi-metrics, hemi-metrics and supermetrics,” e-print, ENS Paris, http://arxiv.org/abs/math.MG/0201011, 2002.
8. M. Deza, V.P. Grishukhin, and M. Laurent, “The symmetries of the cut polytope and of some relatives,” in Applied geometry and discrete mathematics, volume 4 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pp. 205-220. Amer. Math. Soc., Providence, RI, 1991.
9. M. Deza and M. Laurent, Geometry of Cuts and Metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997.
10. I.A. Farad\check zev, M.H. Klin, and M.E. Muzichuk, “Cellular rings and groups of automorphisms of graphs,” in Investigations in Algebraic Theory of Combinatorial Objects, volume 84 of Math. Appl. (Soviet Ser.), pp. 1-152. Kluwer Acad. Publ., Dordrecht, 1994.
11. J.E. Humphreys, Reflection groups and Coxeter groups, volume 29 of Cambridge Studies in Advanced Mathematics, Cambridge University Press, Cambridge, 1990.
12. M.C. Klin, R.P\ddot oschel, and K. Rosenbaum, Angewandte Algebra f\ddot ur Mathematiker und Informatiker. VEB Deutscher Verlag der Wissenschaften, Berlin,
1988. Einf\ddot uhrung in gruppentheoretisch-kombinatorische Methoden. [Introduction to group-theoretical combinatorial methods].
13. M.H. Klin, A study of algebras of invariant relations of certain classes of permutation groups, PhD thesis, NKI and Kiev State University, 1974.
14. M. Laurent, “Graphic vertices of the metric polytope,” Discrete Math. 151(1-3) (1996),131-153,. Graph theory and combinatorics (Manila, 1991).