Embeddings of ultrametric spaces in finite dimensional structures. (English) Zbl 0639.51018

An ultrametric space (X,d) is a metric space whose distance function d satisfies the strong triangle inequality d(x,z)\(\leq \max (d(x,y),d(y,z))\). Motivated by applications in theoretical physics and combinatorial optimization the authors study the problem of embedding a finite ultrametric space (X,d) in certain metric spaces such as the space of subsets of an n-elements set, the hypercube of dimension n, \({\mathbb{R}}^ n\) with the Euclidean distance. Their basic theorem says that in each of these cases \(| X| \leq n+1,\) this bound being attained. Further, the general embedding problem is examined, and an extension to the case of spaces in which almost every triangle satisfies the strong triangle inequality.
Reviewer: F.D.Veldkamp


51K05 General theory of distance geometry
05A99 Enumerative combinatorics
82D30 Statistical mechanics of random media, disordered materials (including liquid crystals and spin glasses)
Full Text: DOI


[1] Baldi, P. F.; Baum, E. B., Bounds on the size of ultrametric structures, Phys. Review Lett., 56, 1598, (1986)
[2] Blumenthal, L., Distance geometries, The University of Missouri Studies, 13, 56, (1938) · Zbl 0019.32903
[3] Ultrametricity transition in the graph coloring problem1985preprint
[4] Jardine, Nicholas; Sibson, Robin, Mathematical taxonomy, (1971) · Zbl 0322.62065
[5] Kirkpatrick, S.; Toulouse, G., Configuration space analysis of travelling salesman problems, J. Physique, 46, 1277, (1985)
[6] Mézard, M.; Parisi, G.; Sourlas, N.; Toulouse, G.; Virasoro, M., Replica symmetry breaking and the nature of the spin Glass phase, J. Physique, 45, 843, (1984) · Zbl 0968.82528
[7] Mézard, M.; Virasoro, M. A., The microstructure of ultrametricity, J. Physique, 46, 1293, (1985)
[8] Parga, N.; Virasoro, M. A., The ultrametric organization of memories in a neural network, J. Physique, 47, 1857, (1986)
[9] Ryser, H. J., An extension of a theorem of de Bruijn and erdo˝s on combinatorial designs, J. Algebra, 10, 246, (1968) · Zbl 0167.28001
[10] Spencer, Joel, Turán’s theorem for k-graphs, Discrete Math., 2, 183, (1972) · Zbl 0237.05116
[11] Tylkin, M. E., On the geometry of the Hamming cube, Dokl. Akad. USSR, 134, 1037, (1960)
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.