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
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
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.