Embedding tree metrics into low-dimensional Euclidean spaces (Q1577550)

The article under review is a valuable contribution in a common field of geometry, graph, complexity and probability theory. It is concerned with embedding metrics induced by trees into Euclidean spaces (of dimension \(d\), e.g., \(\ell^d_p\); or spheres). Given metric spaces \(M= (X,\rho)\), \(M'= (Y,\mu)\), the contraction \(D_c(f)\) of a map \(f: X\to Y\) is the supremum over \(\rho(x, y)\) divided by \(\mu(f(x), f(y))\). The distortion is defined by \(D(f)= D_c(f)\cdot D_e(f)\), where the expansion \(D_c(f)\) is the supremum over the reverse relation. Herewith, the distortion of an embedding \(f\) is the maximum factor by which any distance is changed by the embedding. The main results consist in improving the efficiency of computing \(D(f)\). By an analysis of embedding, the author shows that any weighted tree with \(n\) vertices and \(L\) leaves can be embedded with \(D(f)= \widetilde O(L^{1/(d-1)})\). Then, he studies the embedding of stars proving distortions \(\Omega(L^{1/d})\), \(O(L^{1/d})\) in the unweighted and weighted case, respectively. By applying random projection arguments (under Gaussian distribution) and Lovász local lemma, the research finally arrives at \(D(f) =\widetilde O(n^{1/d})\) for a special tree class. Appendices on spherical codes and constructive examples conclude the article. In future, a number of applications may be expected in coding theory, geometrical data analysis, graph drawing or biomathematics.