Annals of Combinatorics 2 (1998) 211-241Metrics 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
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 d^{H} of a graph H with |Π(d^{H})|=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. |