Naslov
The hypermetric cone and polytope on eight vertices and some generalizations

Autori
Deza, Michel ; Dutour Sikirić, Mathieu

Izvornik
Journal of symbolic computation (0747-7171) 88 (2018), SI; 67-84

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Delaunay polytopes ; Central symmetry ; Cut polytope ; Hypermetric

Sažetak
The paper deals with geometric constraints on Delaunay polytopes, arising from hypermetric inequalities with origins in lattice theory. In some cases the constraints are sufficient to uniquely define a Delaunay polytope, a situation of primary interest in combinatorial rigidity ; and the configuration space of underconstrained Delaunay polytopes defines a face of the hypermetric cone. Symbolic algorithms and computations algorithms form the basis of the paper's results and illustrative examples. The lists of facets - 298592 in 86 orbits - and of extreme rays - 242695427 in 9003 orbits - of the hypermetric cone HYP(8) are computed. The notion of hypermetric occurs in Metric Geometry and realization spaces of Delaunay polytopes in lattices and we consider a number of generalizations. The first one is the hypermetric polytope HYPP(n), for which we give general algorithms and a description for n<=8. We give a complete theory of it and of its link to centrally symmetric Delaunay polytope. Then we shortly consider generalizations to the case of lattice Delaunay simplices of index higher than 1. The case of hypermetrics on graphs is also considered and we show how one can obtain new valid inequalities for the cut-polytope of a graph. We then consider shortly the case of infinite hypermetrics.

Izvorni jezik
Engleski

Znanstvena područja
Matematika, Računarstvo

POVEZANOST RADA