The tight span of an antipodal metric space - Part I: Combinatorial properties

The tight span of a finite metric space (X, d) is the metric space T(X, d) consisting of the compact faces of the polytope P (X d) := {f is an element of R-X : f (x) + f (y) > d(x, y) for all X, y is an element of X), endowed with the metric induced by the l(infinity)-norm on R-X. In this paper, we study T (X, d) in case d is antipodal i.e., in case there is a map sigma: X -> 2(X) - {0} with d(x, y) + d(y, z) = d(x, z) holding for all x, y is an element of X and Z is an element of sigma(x). In particular, we derive combinatorial results concerning the polytopal structure of the tight span of an antipodal metric space, proving that T(X, d) has a unique maximal cell (i.e. a cell containing all other cells) if and only if (X, d) is antipodal, and that in this case there is a bijection between the facets of T(X, d) and the edges in the so-called underlying graph of (X, d). (c) 2005 Elsevier B.V. All rights reserved.