TITLE   : Embedding Metric Spaces in their Intrinsic Dimension

AUTHORS : Ittai Abraham, Yair Bartal, Ofer Neiman

ABSTRACT:

A fundamental question in the theory of metric embedding is
whether the {\em metric dimension} of a metric space is related to
its {\em intrinsic dimension}. That is whether the dimension in
which it can be embedded in some real normed space is implied by
the intrinsic dimension which is reflected by the inherent
geometry of the space.

The intrinsic dimension of a metric space $X$ is naturally measured
by the doubling constant of the space: the minimum $\lambda$ such
that every ball can be covered by $\lambda$ balls of half the
radius. The doubling dimension of $X$ is defined as $\ddim(X) =
\log_2 \lambda$.

Assouad conjectured that every metric space $X$ embeds into
Euclidean space with dimension and distortion depending solely on
$\ddim(X)$. While Assouad's original conjecture was disproved, we
show that by slightly relaxing the demand on the distortion,
$\ddim(X)$ indeed determines the Euclidean dimension.

Our main theorem states that every finite metric space $X$ embeds
into Euclidean space with dimension  $O(\ddim(X))$ and distortion
$O(\log^{1+\varepsilon} n)$, for any $\varepsilon>0$. Moreover, our
embedding posses small average distortion.