Weak similarities of finite ultrametric and semimetric spaces (Q1616628)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Weak similarities of finite ultrametric and semimetric spaces |
scientific article |
Statements
Weak similarities of finite ultrametric and semimetric spaces (English)
0 references
7 November 2018
0 references
Let \((X, d)\) and \((Y, \rho)\) be semimetric spaces. We say that \((X, d)\) and \((Y, \rho)\) are weakly similar if there are a bijection \(\Phi : X \to Y\) and a strictly increasing function \(f : [0, \infty) \to [0, \infty)\) such that the equality \[ f(d(x, y)) = \rho(\Phi(x), \Phi(y)) \] holds for all \(x\), \(y \in X\). The author mainly studies the weak similarities of finite ultrametric spaces. It was proved in [\textit{V. Gurvich} and \textit{M. Vyalyi}, Discrete Appl. Math. 160, No. 12, 1742--1756 (2012; Zbl 1245.05058)] that for every finite ultrametric space \(X\) there is a monotone, rooted tree \(T_X\), the representing tree of \(X\), such that any two finite ultrametric spaces are isometric if and only if the corresponding representing trees are isomorphic as directed, weighted graphs. The author notes that, for finite, weakly similar, ultrametric spaces \(X\) and \(Y\), the trees \(T_X\) and \(T_Y\) are isomorphic as rooted trees but the converse is not valid in general. The main result of the paper, Theorem 2.6, is a characterization of finite ultrametric spaces \(X\) for which the isomorphism of \(T_X\) and \(T_Y\) implies that \(X\) and \(Y\) are weakly similar for every finite ultrametric space \(Y\). A similar result, Theorem 2.7, is also proved for the case when \(X\) is a finite ultrametric space such that different internal nodes of \(T_X\) have different weights. Moreover, the author studies the Hasse diagrams of sets of balls ordered by inclusion of finite semimetric spaces and proves that weakly similar, finite, semimetric spaces have isomorphic Hasse diagrams.
0 references
ultrametric space
0 references
rooted tree
0 references
week similarity
0 references
isomorphism of rooted trees
0 references
0 references