Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I just started (independent) learning on metric embeddings from the Fall 2003 offering of the course at CMU. I have a limited mathematical background and alas, it made me stumble at the first exercise problem of this course.

There are $2$ parts to the problem. I did the first part which asks to isometrically embed a finite arbitrary metric space $(X,d)$ into $\ell_\infty$ using $n-1$ coordinates. Its the second part of the problem where I am out of ideas.

It asks us to embed a finite tree metric $(V,d)$ isometrically into $\ell_\infty$ using only $O(\log{n})$ coordinates. I understand we want to setup functions $f_i\ \colon V \to R$ for all $i \in S$ where $S$ is some set of cardinality $O(\log{n})$. I wanted to take the set $S$ to be the set of vertices with degree at least $3$ but it did not seem to help with the problem as number of these vertices could be linear in $n$. I wondered if we really want to take $S$ as a subset of $V$ but was not able to come up with any alternatives.

I understand that this is probably a pretty basic question, but I would really appreciate some help with this as I am really stuck here.

Please help when you get time.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.