Metric extensions and the L1 hierarchy

AbstractA finite semimetric is L1-embeddable if it can be expressed as a non-negative combination of Hamming semimetrics. A finite semimetric is called hypermetric if it satisfies the (2k+1)-gonal inequalities which naturally generalize the triangle inequality. It is known that all L1-embeddable semimetrics are hypermetric and the metric induced by K7−P3 is hypermetric but not L1-embeddable. In the first part of the paper we show that there are infinite metrics that are hypermetric but are not L1-embeddable, answering a question of Deza. We introduce the r-extension of a semimetric: this is the addition of new points from which all of the distances are r. We show that all 2-extensions of K7−P3 are hypermetric. Unfortunately, 2-extensions of hypermetrics in which all of the distances are either one or two may not be hypermetric in general. We illustrate this by showing that the metric induced by the star K1,5 (which is hypermetric) has a nonhypermetric 2-extension involving three additional points.In the second part of the paper, we show that 1-extensions of the metric induced by K4−P3 form a family that span a hierarchy of metrics that contain L1. A finite semimetric is of negative type if it is the square of a semimetric that can be isometrically embedded in Euclidean space. It is known that a semimetric that is hypermetric is of negative type; and the distance matrix of a semimetric of negative type has one positive eigenvalue. All of the inclusions in the above hierarchy are strict. We demonstrate this latter fact by the 1-extensions of K4−P3. Indeed, K6−P3 is L1-embeddable and K7−P3 is hypermetric but not L1-embeddable. Here we show that K8−P3 is hypermetric but K9−P3 is not; K10−P3 is of negative type but K11−P3 is not; and K11−P3 has one positive eigenvalue but K12−P3 does not. This situation can be contrasted with the collapse of the metric hierarchy for bipartite graphs