The isometries of the cut, metric and hypermetric cones

2003/06/02 by Antoine Deza, Boris Goldengorin, Dmitrii V. Ṗasechnik +1 · 1 citation
Computer Science · Engineering · Mathematics · #Coding theory and cryptography #Finite Group Theory Research #graph theory and CDMA systems #math.GR #math.MG #msc:20F29 #msc:51F99 #msc:51M20 #msc:52B15

paper · pdf · doi:10.1007/s10801-006-6924-6

published as J. Algebraic Combinatorics, 23(2006), 197--203 · 8 pages, LaTeX, 2 postscript figures

arxiv created 2003/06/02 · openalex publication_date 2006/03/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

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; that is, Is(Cut(n))=Is(Met(n))=Sym(n) for n>4. For n=4 we have Is(Cut(4))=Is(Met(4))=Sym(3)xSym(4). This is then 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) for n>4, where Hyp(n) denotes the hypermetric cone.

Citations

• Data mining for cones of metrics, quasi-metrics, hemi-metrics and super-metrics

Cited by

• A counterexample to a conjecture of Laurent and Poljak