Annals of Combinatorics 2 (1998) 211-241


Metrics with Finite Sets of Primitive Extensions

Alexander V. Karzanov

Institute for System Analysis, Russian Academy of Sciences, 9, Prospect 60 Let Oktyabrya, 117312 Moscow, Russia
sasha@cs.isa.ac.ru

Received June 26, 1998

AMS Subject Classification: 05C12, 90C27, 90B10, 57M20

Abstract. In this paper, we give a complete characterization for the class of rational finite metrics μ with the property that the set Π(μ) of primitive extensions of μ is finite. Here, for a metric μ on a set T, a positive extension m of μ to a set V T is called primitive if none of the convex combinations of other extensions of μ to V is less than or equal to m. Our main theorem asserts that the following three properties are equivalent: (i) Π(μ) is finite; (ii) Up to an integer factor,μ is a submetric of the path metric dH of a graph H with |Π(dH)|=1; (iii) A certain bipartite graph associated with μcontains neither isometric k-cycles with k ≥ 6 nor induced subgraphs K-3,3. We then show that Π(μ) is finite if and only if the dimension of the tight span of μ is at most two. We also present other results, discuss applications to multicommodity flows, and raise open problems.

Keywords: finite metric, metric extension, isometric embedding, multicommodity flow, multiterminal cut, tight span


References

1.  A.W.M. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups, Advances in Mathematics 53 (1984) 321–402.

2.  J. Isbell, Six theorems about metric spaces, Comment. Math. Helv. 39 (1964) 65–74.

3.  A.V. Karzanov, Minimum 0-extensions of graph metrics, European J. Combinatorics 19 (1998) 71–101.


Get the LaTex | DVI | PS file of this abstract.

back