Characterization of the Distance between Subtrees of a Tree by the Associated Tight Span

Hiroshi Hirai

Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan

hirai@kurims.kyoto-u.ac.jp

Annals of Combinatorics 10 (1) p.111-128 March, 2006

Abstract:

A characterization is given to the distance between subtrees of a tree defined as the
shortest path length between subtrees. This is a generalization of the four-point condition for tree
metrics. For this, we use the theory of the tight span and obtain an extension of the famous result
by Dress that a metric is a tree metric if and only if its tight span is a tree.

References:

1. H.J. Bandelt and A.W.M. Dress, A canonical decomposition theory for metrics on a finite set, Adv. Math. 92 (1992) 47--105.

2. J.P. Barthélémy and A. Guénoche, Trees and Proximity Representations, Wiley, Chichester, 1991.

3. P. Buneman, The recovery of trees from measures of dissimilarity, In: Mathematics in the Archaeological and Historical Sciences, F.R. Hodson et al., Eds., Edinburgh University Press, Edinburgh, (1971) pp. 387--395.

4. P. Buneman, A note on metric properties of trees, J. Combin. Theory Ser. B 17 (1974) 48--50.

5. M. Chrobak and L.L. Larmore, Generosity helps or an 11-competitive algorithm for three servers, J. Algorithms 16 (1994) 234--263.

6. A.W.M. Dress, Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metric spaces, Adv. Math. 53 (1984) 321--402.

7. A.W.M. Dress, Towards a classification of transitive group actions on finite metric spaces, Adv. Math. 74 (1989) 163--189.

8. A. Dress, V. Moulton, and W. Terhalle, T-theory: an overview, Europ. J. Combin. 17 (1996) 161--175.

9. J. Edmonds, Submodular functions, matroids, and certain polyhedra, In: Combinatorial Structures and their Applications, R. Guy et al., Eds, Gordon and Breach, New York, (1970) pp. 69--87.

10. I.M. Gelfand, R.M. Goresky, R.D. MacPherson, and V.V. Serganova, Combinatorial geometries, convex polyhedra, and Schubert cells, Adv. Math. 63 (1987) 301--316.

11. S. Fujishige, Submodular Functions and Optimization, Annals of Discrete Mathematics, Vol. 47, North-Holland Publishing Co., 1999.

12. H. Hirai, Geometric Study on the Split Decomposition of Finite Metrics, Kyoto University, 2004.

13. H. Hirai and K. Murota, M-convex functions and tree metrics, Japan J. Indust. Appl. Math. 21 (2004) 391--403.

14. J.R. Isbell, Six theorems about injective metric spaces, Comment. Math. Helv. 39 (1964) 65--76.

15. L. Lafforgue, Chirurgie des grassmanniennes, CRM Monogr. Ser. 19, AMS, Providence, RI, 2003.

16. K. Murota, Discrete Convex Analysis, SIAM, Philadelphia, PA, 2003.

17. C. Semple and M. Steel, Phylogenetics, Oxford University Press, Oxford, 2003.

18. J.M.S. Simõoes-Pereira, A note on the tree realizability of a distance matrix, J. Comb. Theory 6 (1969) 303--310.

19. D. Speyer, Tropical linear spaces, arXiv:math.CO/0410455.

20. B. Sturmfels and J. Yu, Classification of six-point metrics, Electron. J. Combin. 11 (2004) #R44.

21. N. Tomizawa, Theory of hyperspaces (XVI) — On the structure of hedrons (in Japanese), In: Papers of the Technical Group on Circuit and System Theory, Institute of Electronics and Communication Engineer of Japan, CAS82–174, 1983.

22. R.J. Vanderbei, Linear Programming, 2nd Ed., Kluwer, Boston, 2001.

23. K.A. Zareckiĭ;, Constructing a tree on the basis of a set of distances between the hanging vertices, Uspehi Mat. Nauk 20 (1965) 90--92.