On the structure of the tight-span of a totally split-decomposable metric (Q820090)

Totally split-decomposable finite metric spaces were introduced by \textit{Hans-Jürgen Bandelt} and \textit{A. W. M. Dress} [Adv. Math. 92, No.~1, 47--105 (1992; Zbl 0789.54036)]. They are used in the field of phylogenetic analysis (e.g. see \textit{A. Dress, D. Huson}, and \textit{V. Moulton} [Discrete Appl. Math. 71, No.~1--3, 95--109 (1996; Zbl 0879.92020)]). The tight span \(T(X,d)\) of a finite metric space \((X,d)\) consists of the bounded faces of the polyhedron \(P(X,d)=\{f\in\mathbb R^X\mid f(x)+f(y)\geq d(x,y)\) for all \(x,y\in X\}\). It was introduced by \textit{J. R. Isbell} [Comment. Math. Helv. 39, 65--76 (1964; Zbl 0151.30205)] and subsequently rediscovered by \textit{A. W. M. Dress} [Adv. Math. 53, 321--402 (1984; Zbl 0562.54041)]. Since the authors believe that a better knowledge of the structure of the tight span of totally split-decomposable finite metric spaces would ultimately provide improved phylogenetic techniques, they have recently studied the tight span of finite metric spaces intensively. Their insights led to the conjecture formulated in [\textit{K. T. Huber, J. H. Koolen}, and \textit{V. Moulton}, Discrete Comput. Geom. 31, No.~4, 567--586 (2004; Zbl 1081.52015)] that a finite metric space \((X,d)\) is totally split-decomposable if and only if every cell in \(T(X,d)\) is \(X\)-gated, i.e. if and only if \((X,d)\) is cell-decomposable. The main result of this paper shows that at least the following is true. Theorem. Every totally split-decomposable finite metric space is cell-decomposable. As a consequence the authors can prove that for a totally split-decomposable finite metric space \((X,d)\) every cell in \(T(X,d)\) is a zonozope, that is polytope isomorphic either to a hypercube or to a rhombic dodecahedron.