| Hiroshi Maehara (2008) | |||||||||||||||
Abstract | |||||||||||||||
| Afinite semimetric is L 1 − embeddable if it can be expressed as a nonnegative combination of Hamming semimetrics. Afinite semimetric is called hypermetric if it satisfies the (2k + 1) − gonal inequalities which naturally generalize the triangle inequality. Itisknown that all L 1 − embeddable semimetrics are hypermetric and the metric induced by K 7 − P 3 is hypermetric but not L 1 − embeddable. In the first part of the paper we show that there are infinite metrics that are hypermetric but are not L 1 − embeddable, answering a question of M. Deza. We introduce the r − extension of a semimetric: this is the addition of new points from which all of the distances are r. Weshow that all 2-extensions of K 7 − P 3 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 K 1,5 (which is hypermetric) has a nonhypermetric 2-extension involving three additional points. In the second part of the paper, weshow that 1-extensions of the metric induced by K 4 − P 3 form a family that span a hierarchy ofmetrics that contain L 1.Afinite semimetric is of 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 K 4 − P 3. Indeed, K 6 − P 3 is L 1 − embeddable and K 7 − P 3 is hypermetric but not L 1 − embeddable. Here we show that K 8 − P 3 is hypermetric but K 9 − P 3 is not; K 10 − P 3 is of negative type but K 11 − P 3 is not; and K 11 − P 3 has one positive eigenvalue but K 12 − P 3 does not. This situation can be contrasted with the collapse of the metric hierarchy for bipartite graphs. 1. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||