Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Croatian Scientific ...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Cones of metrics, quasimetrics and hemimetrics

Authors: Deza, Michel; Dutour Sikirić, Mathieu;

Cones of metrics, quasimetrics and hemimetrics

Abstract

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.

Country
Croatia
Keywords

Polytope ; Group ; Metric

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average