Geodesic
The hypermetric cone and polytope on graphs
Čebyševskij sbornik, Tome 20 (2019) no. 2, pp. 169-177.

Voir la notice de l'article provenant de la source Math-Net.Ru

The hypermetric cone was defined in [9] and was extensively studied by Michel Deza and his collaborators. Another key interest of him was cut and metric polytope which he considered in his last works in the case of graphs. Here we combine both interest by considering the hypermetric on graphs. We define them for any graph and give an algorithm for computing the extreme rays and facets of hypermetric cone on graphs. We compute the hypermetric cone for the first non-trivial case of $K_7 - \{e\}$. We also compute the hypermetric cone in the case of graphs with no $K_5$ minor.
Keywords: algebraic lattices, algebraic net, trigonometric sums of algebraic net with weights, weight functions. 
@article{CHEB_2019_20_2_a11,
     author = {M. Dutour},
     title = {The hypermetric cone and polytope on graphs},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {169--177},
     publisher = {mathdoc},
     volume = {20},
     number = {2},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2019_20_2_a11/}
}
TY  - JOUR
AU  - M. Dutour
TI  - The hypermetric cone and polytope on graphs
JO  - Čebyševskij sbornik
PY  - 2019
SP  - 169
EP  - 177
VL  - 20
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2019_20_2_a11/
LA  - en
ID  - CHEB_2019_20_2_a11
ER  - 
%0 Journal Article
%A M. Dutour
%T The hypermetric cone and polytope on graphs
%J Čebyševskij sbornik
%D 2019
%P 169-177
%V 20
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2019_20_2_a11/
%G en
%F CHEB_2019_20_2_a11
M. Dutour. The hypermetric cone and polytope on graphs. Čebyševskij sbornik, Tome 20 (2019) no. 2, pp. 169-177. http://geodesic.mathdoc.fr/item/CHEB_2019_20_2_a11/

[1] F. Barahona, “The max-cut problem on graphs not contractible to $K_{s}$”, Oper. Res. Lett., 2:3 (1983), 107–111 | MR | Zbl

[2] F. Barahona, “On cuts and matchings in planar graphs”, Math. Programming, Ser. A, 60:1 (1993), 53–68 | MR | Zbl

[3] E. P. Baranovskiĭ, “Volumes of $L$-simplexes of five-dimensional lattices”, Mat. Zametki, 13 (1973), 771–782 | MR | Zbl

[4] E. P. Baranovskii, “About l-simplexes of $6$-dimensional lattices”, Second International conference “Algebraic, Probabilistic, Geometrical, Combinatorial and Functional Methods in the theory of numbers”, 1995 (in russian)

[5] E. P. Baranovskii, “The conditions for a simplex of $6$-dimensional lattice to be $l$-simplex”, Nauch. Trud. Ivan., 1999, no. 2, 18–24 (in russian) | MR

[6] A. Deza, B. Goldengorin, D. V. Pasechnik, “The isometries of the cut, metric and hypermetric cones”, J. Algebraic Combin., 23:2 (2006), 197–203 | MR | Zbl

[7] M. Deza, M. Dutour, “The hypermetric cone on seven vertices”, Experiment. Math., 12:4 (2003), 433–440 | MR | Zbl

[8] M. Deza, M. Dutour Sikirić, “The hypermetric cone and polytope on eight vertices and some generalizations”, J. Symbolic Comput., 88 (2018), 67–84 | MR | Zbl

[9] M. Deza, V. P. Grishukhin, M. Laurent, “Extreme hypermetrics and $L$-polytopes”, Sets, graphs and numbers (Budapest, 1991), Colloq. Math. Soc. János Bolyai, 60, North-Holland, Amsterdam, 1992, 157–209 | MR | Zbl

[10] M. Deza, V. P. Grishukhin, M. Laurent, “Hypermetrics in geometry of numbers”, Combinatorial optimization (New Brunswick, NJ, 1992–1993), DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 20, Amer. Math. Soc., Providence, RI, 1995, 1–109 | MR | Zbl

[11] M. Deza, M. D. Sikirić, “Enumeration of the facets of cut polytopes over some highly symmetric graphs”, Int. Trans. Oper. Res., 23:5 (2016), 853–860 | MR | Zbl

[12] M. M. Deza, M. Laurent, Geometry of cuts and metrics, Algorithms and Combinatorics, 15, Springer, Heidelberg, 2010 (First softcover printing of the 1997 original [MR1460488]) | MR | Zbl

[13] M. Dutour, “The six-dimensional Delaunay polytopes”, European J. Combin., 25:4 (2004), 535–548 | MR | Zbl

[14] M. Dutour Sikirić, “The seven dimensional perfect Delaunay polytopes and Delaunay simplices”, Canad. J. Math., 69:5 (2017), 1143–1168 | MR | Zbl

[15] M. Dutour Sikirić, M. M. Deza, E. I. Deza, “Computations of metric/cut polyhedra and their relatives”, Handbook of geometric constraint systems principles, Discrete Math. Appl. (Boca Raton), CRC Press, Boca Raton, FL, 2019, 213–231 | MR | Zbl

[16] M. Dutour Sikirić, V. Grishukhin, “How to compute the rank of a Delaunay polytope”, European J. Combin., 28:3 (2007), 762–773 | MR | Zbl

[17] M. Dutour Sikirić, A. Schürmann, F. Vallentin, “Inhomogeneous extreme forms”, Ann. Inst. Fourier (Grenoble), 62:6 ((2013) 2012), 2227–2255 | MR

[18] R. Erdahl, “A cone of inhomogeneous second-order polynomials”, Discrete Comput. Geom., 8:4 (1992), 387–416 | MR | Zbl

[19] U. Fincke, M. Pohst, “Improved methods for calculating vectors of short length in a lattice, including a complexity analysis”, Math. Comp., 44:170 (1985), 463–471 | MR | Zbl

[20] S. S. Ryshkov, E. P. Baranovskii, “Repartitioning complexes in $n$-dimensional lattices (with full description for $n\leq 6$)”, Proceedings of conference “Voronoi impact on modern science”, v. 2, 1998, 115–124 | Zbl

[21] P. D. Seymour, “Matroids, multicommodity flows”, European J. Combin., 2:3 (1981), 257–290 | MR | Zbl