LOW DISTORTION EUCLIDEAN EMBEDDINGS OF TREES

We 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. We introduce the notation c(2)(X, d) for the least disto rtion with which the metric space (X, d) may be embedded in a Euclidea n space. It is known that if (X, d) is a metric space with n points, t hen c(2)(X, d) less than or equal to 0(log n) and the bound is tight. Let T be a tree with n vertices, and d be the metric induced by it. We show that c(2)(T, d) less than or equal to 0(log log n), that is we p rovide an embedding f of its vertices to the Euclidean space, such tha t d(x, y) less than or equal to parallel to f (x) - f(y) parallel to l ess than or equal to c log log nd(x, y) for some constant c.