  Metric embeddings traditionally study how to map $n$ items to a target metric
space such that distance lengths are not heavily distorted; but what if we only
care to preserve the relative order of the distances (and not their length)? In
this paper, we are motivated by the following basic question: given triplet
comparisons of the form ``item $i$ is closer to item $j$ than to item $k$,''
can we find low-dimensional Euclidean representations for the $n$ items that
respect those distance comparisons? Such order-preserving embeddings naturally
arise in important applications and have been studied since the 1950s, under
the name of ordinal or non-metric embeddings. Our main results are:
  1. Nearly-Tight Bounds on Triplet Dimension: We introduce the natural concept
of triplet dimension of a dataset, and surprisingly, we show that in order for
an ordinal embedding to be triplet-preserving, its dimension needs to grow as
$\frac n2$ in the worst case. This is optimal (up to constant) as $n-1$
dimensions always suffice.
  2. Tradeoffs for Dimension vs (Ordinal) Relaxation: We then relax the
requirement that every triplet should be exactly preserved and present almost
tight lower bounds for the maximum ratio between distances whose relative order
was inverted by the embedding; this ratio is known as (ordinal) relaxation in
the literature and serves as a counterpart to (metric) distortion.
  3. New Bounds on Terminal and Top-$k$-NNs Embeddings: Going beyond triplets,
we then study two well-motivated scenarios where we care about preserving
specific sets of distances (not necessarily triplets). The first scenario is
Terminal Ordinal Embeddings and the second scenario is top-$k$-NNs Ordinal
Embeddings.
  To the best of our knowledge, these are some of the first tradeoffs on
triplet-preserving ordinal embeddings and the first study of Terminal and
Top-$k$-NNs Ordinal Embeddings.
