The isometries of the cut, metric and hypermetric cones

Deza, Antoine ; Goldengorin, Boris ; Pasechnik, Dmitrii V.

Journal of Algebraic Combinatorics, Tome 23 (2006) no. 2, pp. 197-203.

Résumé

Summary: 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,\dots , n} \{1,\dots,n\}$ , that is, $I$s( Cut $n)= I$s( Met $n) @ Sym n Is(\mathrm{Cut}{n})=Is(\mathrm{Met}{n})\simeq $Symn 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 $Sym3$\times $Sym4 . 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.

Détail

Keywords: keywords polyhedral combinatorics, metric cone, hypermetric cone, symmetry group