Naslov
Cones and polytopes of metrics, hypermetrics, quasimetrics and hemimetrics

Autori
Dutour Sikirić, Mathieu

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, pp prezentacija, znanstveni

Skup
XVI International Conference, dedicated to the 80th anniversary of the birth of Professor Michel Deza

Mjesto i datum
Tula, Ruska Federacija, 13.05.2019. - 17.05.2019

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
Metric ; Polytope ; Enumeration

Sažetak
I will present the works that I did with Michel on metric cones and related subjects. We can define the cone of metric on a finite point set X. That is the set of real functions on X^2 satisfying the triangle inequality and the symmetric relation. It is a polyhedral cone that we call MET(K_n). A very interesting subset of this cone is the cone of L^1 embeddable metrics, which we call CUT(K_n). The vertices/facets of those cones are known up to n=8. The definition of the metric and cut cone can be extended to an arbitrary graph G. The triangle inequalities are replaced by cycle inequalities and non-negative inequalities. In that setting, we have CUT(G) = MET(G) is and only if G does not have a K5 minor. This allows to compute the facets of many cut polytopes and is a remarkable result. Another generalization that we consider is to hypermetrics. This generalization is relevant to the geometry of numbers and Delaunay polytopes and we computed their dual description up to n=8. We also present the construction of hypermetric polytopes. One natural generalization of metrics is to consider the cone of quasimetrics defined as real functions on X^2 satisfying the triangular inequalities but are not necessarily symmetric. In that setting, we define a notion of the metric polytope of a graph that we call QMET(G) and we give an explicit set of inequalities describing it that generalizes the one for MET(G). We define the notion of oriented metrics that are weighable and an oriented version of the cuts. Another generalization is to consider the notion of metrics on more than 2 points, i.e. hemimetrics. In that setting, the equivalent of the triangle inequality would be the inequality over a simplex. However, it turns out that this definition is not workable since it does not allow to define the hemimetrics on a simplicial complex. We give another set of inequalities that allow a neat generalization to the case of an arbitrary complex.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA