Naslov
Cones of metrics, quasimetrics and hemimetrics

Autori
Deza, Michel ; Dutour Sikirić, Mathieu

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

Skup
Franco-Japanese Days on Combinatorics and Optimization 2017 - In Honour of Michel Deza -

Mjesto i datum
Tokyo, Japan, 04.12.2017. - 05.12.2017

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Međunarodna recenzija

Ključne riječi
Polytope ; Group ; Metric

Sažetak
In this talk, I will present the works that we did together on the subject of 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 symmetry and triangle inequality. 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. We shortly present the algorithms that were used for the computation of the facets of polytopes given by their vertices. The programs are freely available on the second author web page. Some applications to the Bell polytopes are presented. We also shortly present the hypermetrics. 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) if 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. One natural generalization of metrics is to consider the cone of quasi-metric defined as functions satisfying the triangle inequality but not necessarily the symmetry. 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

POVEZANOST RADA