×

zbMATH — the first resource for mathematics

Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces. (English) Zbl 0562.54041
A metric space Y is injective if every mapping which increases no distance from a subspace of any metric space X to Y can be extended, increasing no distance, over X. In 1964, J. R. Isbell constructed an injective envelope \(T_ X\) of a metric space X [see Comment. Math. Helv. 39, 65-76 (1964; Zbl 0151.302)]. The present paper brings a thorough analysis of this construction and applications of it to (1) the existence of embeddings of metric spaces into trees, (2) optimal graphs realizing a metric space, and (3) the cohomological dimensions of groups with specific length functions. In more detail, a metric space X is a tree if for any two elements x,y\(\in X\) there is - up to a parametrization - only one injective continuous map \(h: [0,1]\to X\) such that \(h(0)=x\) and \(h(1)=y\). Now, \(T_ X\) tests the embeddability of X into a tree, i.e. X is a subspace of a tree if and only if \(T_ X\) is a tree. The relation of \(T_ X\) to optimal realizations of X by networks is a little weaker: any optimal realization of X is contained in \(T_ X\).
Reviewer: J.Rosicky

MSC:
54E35 Metric spaces, metrizability
54C20 Extension of maps
05C99 Graph theory
20J99 Connections of group theory with homological algebra and category theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] \scH. J. Bandelt and A. Dress, Reconstructing the shape of a tree from observed dissimilarity data, in preparation. · Zbl 0613.62083
[2] \scM. Bourque, Arbres de Steiner et reseaux dont certains sommets sont a localisation variable, Ph.D. thesis, Université de Montréal, Montréal, Canada.
[3] Buneman, P, A note on the metric properties of trees, J. combin. theory ser. B, 17, 48-50, (1974) · Zbl 0286.05102
[4] Chiswell, I.M, Abstract length functions in groups, (), 451-463 · Zbl 0351.20024
[5] Cunningham, J.P, Free trees and bidirectional trees as representations of psychological distance, J. math. psych., 17, 165-188, (1978) · Zbl 0383.94041
[6] Day, W.H.E, Distributions of distances between pairs of classifications, (), 127-131
[7] Dobson, A.J, Unrooted trees for numerical taxonomy, J. appl. probab., 11, 32-42, (1974) · Zbl 0277.92004
[8] Fitch, W.M, A non-sequential method for constructing trees and hierarchical classifications, J. mol. evol., 18, 30-37, (1981)
[9] Goldmann, A.J, Realizing the distance matrix of a graph, J. res. nat. bur. standards sect. B, 70, 153-154, (1966) · Zbl 0151.33301
[10] Hakimi, S.L; Yau, S.S, Distance matrix of a graph and its realizability, Quart. appl. math., XXII, 305-317, (1965) · Zbl 0125.11804
[11] Hoare, A.H.M, On length functions and nielson methods in free groups, J. London math. soc., 14, 188-192, (1976) · Zbl 0349.20011
[12] Hoare, A.H.M, An embedding for groups with length functions, Mathematika, 26, 99-102, (1979) · Zbl 0403.20020
[13] Imrich, W, Realisierung von metriken in graphen, Österreich. akad. wiss. math.—natur. kl. sitzungsber. II, 178, 19-24, (1969) · Zbl 0193.24602
[14] Imrich, W; Stotskii, E, Optimal embeddings of metrics in graphs, Siberian math. J., Dokl. akad. nauk. SSSR, 200, 279-281, (1971)
[15] Imrich, W, On metric properties of tree-like spaces, (), 129-156
[16] Imrich, W; Schwarz, G, Trees and length functions on groups, Ann. discrete math., 17, 347-359, (1982) · Zbl 0536.20021
[17] Lyndon, R.C, Length functions in groups, Math. scand., 12, 209-234, (1963) · Zbl 0119.26402
[18] Meacham, C.A, A manual method for character compatibility analysis, Taxon, 30, 591-600, (1981)
[19] Meacham, C.A, A probability measure for character compatibility, Math. biosci., 57, 1-18, (1981) · Zbl 0478.92003
[20] Mulder, H.M, The structure of Median graphs, Discrete math., 24, 197-204, (1978) · Zbl 0394.05038
[21] Nagata, J.I, Modern dimension theory, (1965), Wiley New York
[22] Patrinos, A.N; Hakimi, S.L, The distance matrix of a graph and its tree realization, Quart. appl. math., (October 1972)
[23] Penny, D; Foulds, L.R; Hendy, M.D, Testing the theory of evolution by comparing phylogenetic trees constructed from five different protein sequences, Nature, 297, 197-200, (1982)
[24] Robinson, D.F; Foulds, L.R, Comparison of phylogenetic trees, Math. biosci., 53, 131-147, (1981) · Zbl 0451.92006
[25] Rohlf, F.J, Numbering binary trees with labeled terminal vertices, Bull. math. biol., 45, 33-40, (1983) · Zbl 0513.05027
[26] Rourke, C.P; Sanderson, B.J, Introduction to piecewise-linear topology, (1972), Springer Berlin · Zbl 0254.57010
[27] Sattah, S; Tversky, A, Additive similarity trees, Psychometrika, 42, 319-345, (1977)
[28] Simões-Pereira, J.M.S, A note on the tree realizability of a distance matrix, J. combin. theory, 6, 303-310, (1969) · Zbl 0177.26903
[29] Simões-Pereira, J.M.S; Zamfirescu, C.M, Submatrices of ńon-tree-realizable distance matrices, Linear algebra appl., 44, 1-17, (1982) · Zbl 0483.05045
[30] Serre, J.-P, Groupes discrets, (1969-1970), Extrait de l’Annuaire du Collège de France · Zbl 0174.31301
[31] Stotskii, E.D, Embedding of finite metrics in graphs, Siberian math. J., 5, 1203-1206, (1964) · Zbl 0139.17302
[32] Tignol, J.-P, Remarque sur le groupe des automorphismes d’un arbre, Ann. soc. sci. bruxelles, 93, 196-202, (1979) · Zbl 0435.20003
[33] Tits, J, Sur le groupe des automorphismes d’un arbre, (), 188-211 · Zbl 0214.51301
[34] Tits, J, A “theorem of Lie-kolchin” for trees, (), 377-388
[35] Waterman, M.S; Smith, T.F, On the similarity of dendrograms, J. theoret. biol., 73, 789-800, (1978)
[36] Waterman, M.S; Smith, T.F; Singh, M; Beyer, W.A, Additive evolutionary trees, J. theoret. biol., 64, 199-213, (1977)
[37] Wilkens, D.L, Length functions and normal subgroups, J. London math. soc., 22, 439-448, (1980) · Zbl 0448.20037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.