Low distortion Euclidean embeddings of trees (Q1269777)

The authors consider the problem of embedding a certain finite metric space to the Euclidean space, trying to keep the bi-Lipschitz constant as small as possible. Let \(c_2(X,d)\) be the least distortion with which the metric space \((X,d)\) may be embedded in a Euclidean space. It is known [\textit{J. Bourgain}, Isr. J. Math. 52, 46-52 (1985; Zbl 0657.46013)] that if \((X,d)\) is a metric space with \(n\) points, then \(c_2(X,d)\leq O(\log n)\) and the bound is tight. Main result of the present paper is the following: Let \(T\) be a tree with \(n\) vertices, and \(d\) be the metric introduced by it, then \(c_2(T,d)\leq O(\log\log n)\).