The isometries of the cut, metric and hypermetric cones

Antoine Deza; Boris Goldengorin; Dmitrii V. Pasechnik

doi:10.1007/s10801-006-6924-6

The isometries of the cut, metric and hypermetric cones

Antoine Deza, Boris Goldengorin, Dmitrii V. Pasechnik^*

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

7 Scopus citations

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, I s(Cut_n) = I s(Met_n) ≃ Sym(n) for n ≥. For n = 4 we have I s(Cut₄) = I s(Met ₄) ≃ Sym(3) × 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, I s(Hyp_n) ≃ Sym(n) for n ≥ 5, where Hyp_n denotes the hypermetric cone.

Original language	English (US)
Pages (from-to)	197-203
Number of pages	7
Journal	Journal of Algebraic Combinatorics
Volume	23
Issue number	2
DOIs	https://doi.org/10.1007/s10801-006-6924-6
State	Published - Mar 2006
Externally published	Yes

Funding

The first author is partially supported by the NSREC under the Canada Research Chair and the Discovery Grant programs. The work was completed while the third author held a position at CS Dept. of University of Frankfurt, supported by the DFG Grant SCHN-503/2-1. The second and the third author acknowledge support by the Research School SOM of the University of Groningen.

Keywords

Hypermetric cone
Metric cone
Polyhedral combinatorics
Symmetry group

ASJC Scopus subject areas

Algebra and Number Theory
Discrete Mathematics and Combinatorics

Access to Document

10.1007/s10801-006-6924-6

Cite this

@article{8da7dff62abc4ef3bfbfe519b11b98a5,

title = "The isometries of the cut, metric and hypermetric cones",

abstract = "We show that the symmetry groups of the cut cone Cutn and the metric cone Metn both consist of the isometries induced by the permutations on {1,...,n]; that is, I s(Cutn) = I s(Metn) ≃ Sym(n) for n ≥. For n = 4 we have I s(Cut4) = I s(Met 4) ≃ Sym(3) × 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, I s(Hypn) ≃ Sym(n) for n ≥ 5, where Hypn denotes the hypermetric cone.",

keywords = "Hypermetric cone, Metric cone, Polyhedral combinatorics, Symmetry group",

author = "Antoine Deza and Boris Goldengorin and Pasechnik, {Dmitrii V.}",

year = "2006",

month = mar,

doi = "10.1007/s10801-006-6924-6",

language = "English (US)",

volume = "23",

pages = "197--203",

journal = "Journal of Algebraic Combinatorics",

issn = "0925-9899",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - The isometries of the cut, metric and hypermetric cones

AU - Deza, Antoine

AU - Goldengorin, Boris

AU - Pasechnik, Dmitrii V.

PY - 2006/3

Y1 - 2006/3

N2 - We show that the symmetry groups of the cut cone Cutn and the metric cone Metn both consist of the isometries induced by the permutations on {1,...,n]; that is, I s(Cutn) = I s(Metn) ≃ Sym(n) for n ≥. For n = 4 we have I s(Cut4) = I s(Met 4) ≃ Sym(3) × 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, I s(Hypn) ≃ Sym(n) for n ≥ 5, where Hypn denotes the hypermetric cone.

AB - We show that the symmetry groups of the cut cone Cutn and the metric cone Metn both consist of the isometries induced by the permutations on {1,...,n]; that is, I s(Cutn) = I s(Metn) ≃ Sym(n) for n ≥. For n = 4 we have I s(Cut4) = I s(Met 4) ≃ Sym(3) × 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, I s(Hypn) ≃ Sym(n) for n ≥ 5, where Hypn denotes the hypermetric cone.

KW - Hypermetric cone

KW - Metric cone

KW - Polyhedral combinatorics

KW - Symmetry group

UR - http://www.scopus.com/inward/record.url?scp=33646536972&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646536972&partnerID=8YFLogxK

U2 - 10.1007/s10801-006-6924-6

DO - 10.1007/s10801-006-6924-6

M3 - Article

AN - SCOPUS:33646536972

SN - 0925-9899

VL - 23

SP - 197

EP - 203

JO - Journal of Algebraic Combinatorics

JF - Journal of Algebraic Combinatorics

IS - 2

ER -

The isometries of the cut, metric and hypermetric cones

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this