The hypermetric cone and polytope on eight vertices and some generalizations. (September 2018)

• Record Type: Journal Article
• Authors: Deza, Michel; Dutour Sikirić, Mathieu
• Is Part Of: Journal of symbolic computation. Volume 88(2018)
• Page Start: 67
• Page End: 84
• Publication Date: 2018-09
• Subjects: Delaunay polytopes -- Central symmetry -- Dual description -- Metric cone -- Cut polytope -- Hypermetric; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2016.01.009
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: 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 – 298, 592 in 86 orbits – and of extreme rays – 242, 695, 427 in 9, 003 orbits – of the hypermetric cone H Y P 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 H Y P P 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.