Embeddings of Ultrametric Spaces in Finite Dimensional Structures
Authors:
- Michael AschbacherMAMichael Aschbacher
- Pierre BaldiPBPierre Baldi
- Eric B. BaumEBEric B. Baum
- Richard M. WilsonRWRichard M. Wilson
- 1 October 1987
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 8 (4) , 564-577
Abstract
Motivated by recent advances in theoretical physics and combinatorial optimization, we study the problem of embedding ultrametric spaces into finite dimensional structures: finite sets, Euclidean spaces $\mathbb{R}^n $, Euclidean sphere $S^n $, and n-dimensional hypercube with Hamming distance. We give conditions and constructions of embeddings and show a general upper bound of $n + 1$ on the cardinality of the ultrametric set. We also give an upper bound on the cardinality of quasi-ultrametric sets.
Keywords
This publication has 7 references indexed in Scilit:
- Bounds on the Size of Ultrametric StructuresPhysical Review Letters, 1986
- The ultrametric organization of memories in a neural networkJournal de Physique, 1986
- Configuration space analysis of travelling salesman problemsJournal de Physique, 1985
- The microstructure of ultrametricityJournal de Physique, 1985
- Replica symmetry breaking and the nature of the spin glass phaseJournal de Physique, 1984
- Turán's theorem for k-graphsDiscrete Mathematics, 1972
- An extension of a theorem of de Bruijn and Erdös on combinatorial designsJournal of Algebra, 1968