# A Union of Euclidean Metric Spaces is Euclidean

Konstantin Makarychev  Yury Makarychev Supported by NSF awards CAREER
CCF-1150062 and IIS-1302662.

###### Abstract

Suppose that a metric space $X$ is the union of two metric subspaces $A$ and
$B$ that embed into Euclidean space with distortions $D_{A}$ and $D_{B}$,
respectively. We prove that then $X$ embeds into Euclidean space with a
bounded distortion (namely, with distortion at most
$7D_{A}D_{B}+2(D_{A}+D_{B})$). Our result settles an open problem posed by
Naor. Additionally, we present some corollaries and extensions of this result.
In particular, we introduce and study a new concept of an “external bi-
Lipschitz extension”.

In the end of the paper, we list a few related open problems.

title = A Union of Euclidean Metric Spaces is Euclidean, author = Konstantin
Makarychev and Yury Makarychev, plaintextauthor = Konstantin Makarychev, Yury
Makarychev, keywords = metric geometry, local-global properties, Lipschitz
extension, year=2016, number=14, received=22 March 2016, published=10 August
2016, doi=10.19086/da.876,

[classification=text]

##  1 Introduction

In this paper, we give an affirmative answer to the following question posed
by Assaf Naor.

######  Question 1.

Consider a metric space $X$ that is the union of two metric subspaces $A$ and
$B$. Suppose that $A$ and $B$ embed into Euclidean space with distortions
$D_{A}$ and $D_{B}$, respectively. Does $X$ embed into Euclidean space with
bounded distortion?

We prove that the metric space $X$ embeds into $\ell_{2}$ with distortion at
most $7D_{A}D_{B}+2(D_{A}+D_{B})$.

We note that the question is related to the recent research in theoretical
computer science on local–global properties of metric spaces and the power of
lift–and–project relaxations for combinatorial optimization problems [1, 2,
3]. One of the main goals of this research is to understand how constraints on
relatively small subsets of a metric space affect its global properties. In
particular, Arora, Lovász, Newman, Rabani, Rabinovich, and Vempala [1] asked
the following question.

######  Question 2.

For $n\geq k\geq 1$ and $p\in[1,\infty)$, find the least value of
$D=D_{n,k,p}$ such that the following is true. If $X$ is a finite metric space
on $n$ points such that every $k$-point subset of $X$ isometrically embeds
into $\ell_{p}$, then $X$ embeds into $\ell_{p}$ with distortion at most
$D_{n,k,p}$.

In [2], Charikar, Makarychev, and Makarychev showed that

$c\left(\frac{\log n}{\log k+\log\log n}\right)^{1/p}\leq D_{n,k,p}\leq
C\log(n/k),$

for some positive absolute constants $c$ and $C$. They also showed that an
upper bound of $C(\log(n/k)+\log\log(1/\alpha))$ holds if not all but only an
$\alpha$ fraction of all subsets of size $k$ isometrically embed into
$\ell_{p}$. In contrast, in this paper, we assume only that two subsets of $X$
(subsets $A$ and $B$) embed isometrically into $\ell_{2}$; note that at least
one of them should be of size $n/2$.

|  assumption on subsets of $X$ that embed into $\ell_{p}$ |  |
---|---|---|---
| number of subsets | size of each subset |  distortion with which $X\hookrightarrow\ell_{p}$ |  value of $p$
Q1 |  2, subsets partition $X$ |  avg. size is at least $n/2$ | $O(1)$ | $p=2$
Q2 |  an $\alpha$ fraction of subsets | $k$ | $O(\log(n/k)+\log\log(1/\alpha)$ | $p\in[1,\infty]$
Figure 1: Comparison of the assumptions and guarantees for Questions 1 and 2.

An analog of Question 1 for ultrametrics was studied by Mendel and Naor in
[8]. They showed that if $(X,d)$ is the union of $(A,d)$ and $(B,d)$ that
embed into ultrametric spaces with distortions $D_{A}$ and $D_{B}$, then $X$
also embeds into an ultrametric space with distortion at most
$(D_{A}+2)(D_{B}+2)-2$.

###  1.1 Preliminaries

We denote the $k$ dimensional Euclidean space by $\ell_{2}^{k}$ and the
(separable) Hilbert space by $\ell_{2}^{\infty}$. The Lipschitz constant of a
map $f$ from a metric space $(X,d_{X})$ to a metric space $(Y,d_{Y})$ is
$\|f\|_{Lip}=\sup_{\begin{subarray}{c}x,y\in X\\\ x\neq
y\end{subarray}}\frac{d_{Y}(f(x),f(y))}{d_{X}(x,y)}$. The distortion of an
embedding $f:X\hookrightarrow Y$ is $\|f\|_{Lip}\|f^{-1}\|_{Lip}$ (where
$f^{-1}$ is the inverse map from $f(X)\subset Y$ to $X$).

For a metric space $X$ and a Banach space $V$, let the Lipschitz extension
constant $e_{k}(X,V)$ be the minimal constant $C$ such that the following
holds: for every subset $Y$ of $X$ of size at most $k$ and every map $f:Y\to
V$ there exists an extension $\hat{f}:X\to V$ such that $\|\hat{f}\|_{Lip}\leq
C\|f\|_{Lip}$. In this paper, we use the Kirszbraun theorem that states that
every map $f$ from a subset $Y$ of $\ell_{2}^{a}$ to $\ell_{2}^{b}$ can be
extended to a map $\tilde{f}:\ell_{2}^{a}\to\ell_{2}^{b}$ so that
$\|\tilde{f}\|_{Lip}=\|f\|_{Lip}$; in particular,
$e_{k}(\ell_{2}^{a},\ell_{2}^{b})=1$ for every $k$ [5] (see also [10]).

###  1.2 Our Results

We prove the following theorem that answers Question 1 affirmatively.

######  Theorem 1.1.

Consider a metric spaces $(X,d)$. Assume that $X$ is the union of two metric
subspaces $A$ and $B$ that embed into $\ell_{2}^{a}$ and $\ell_{2}^{b}$ with
distortions $D_{A}$ and $D_{B}$, respectively. Then $X$ embeds into
$\ell_{2}^{a+b+1}$ with distortion at most

$7D_{A}D_{B}+2(D_{A}+D_{B}).$

If $D_{A}=D_{B}=1$, then $X$ embeds into $\ell_{2}^{a+b+1}$ with distortion at
most $8.93$.

In this theorem, $a$ and $b$ may be finite or infinite.

As we show in Lemma 2.9 in Section 2.1, it is sufficient to prove Theorem 1.1
only for finite metric spaces — the result for arbitrary metric spaces follows
from the result for finite metric spaces. So we assume below that $X$ is
finite.

Let ${\cal D}(D_{A},D_{B})$ be the minimal $D$ such that every metric space
$(X,d)$ as in Theorem 1.1 embeds into $\ell_{2}$ with distortion at most $D$.
It is interesting to understand the dependence of ${\cal D}(D_{A},D_{B})$ on
$D_{A}$ and $D_{B}$. The result of Theorem 1.1 can be restated as

${\cal D}(D_{A},D_{B})\leq 7D_{A}D_{B}+2(D_{A}+D_{B})\quad\text{and}\quad{\cal
D}(1,1)<8.93\quad.$

There is a trivial lower bound on ${\cal D}(D_{A},D_{B})$: ${\cal
D}(D_{A},D_{B})\geq\max(D_{A},D_{B})$. We also prove that ${\cal
D}(D_{A},D_{B})\geq 3$.

######  Theorem 1.2.

For every $\varepsilon>0$, there exists a finite metric space $(X,d)$, which
is the union of two metric subspaces $A$ and $B$ such that

  * •

$A$ and $B$ embed into $\ell_{2}^{n-1}$ isometrically (where $n=|A|=|B|$),

  * •

any embedding of $X$ into $\ell_{2}\equiv\ell_{2}^{\infty}$ has distortion at
least $3-\varepsilon$.

We present some corollaries and extensions to Theorem 1.1 in Section 4. In
particular, we introduce and study a new notion of an “external bi-Lipschitz
extension”.

##  2 Proof of Theorem 1.1

In this section, we prove Theorem 1.1. We now give a brief outline of our
proof. Since $A$ embeds into $\ell_{2}^{a}$ with distortion $D_{A}$, and $B$
embeds into $\ell_{2}^{b}$ with distortion $D_{B}$, there are non-contracting
embeddings $\varphi_{A}:A\hookrightarrow\ell_{2}^{a}$ and
$\varphi_{B}:B\hookrightarrow\ell_{2}^{b}$ with $\|\varphi_{A}\|_{Lip}\leq
D_{A}$ and $\|\varphi_{B}\|_{Lip}\leq D_{B}$. Our first goal is to construct a
map $\psi_{B}=\psi:X\to\ell_{2}^{b}$ that is Lipschitz on $X$ and bi-Lipschitz
on $B$ (see Lemma 2.6). We start with proving Lemmas 2.4 and 2.5. We define
$\psi_{B}$ by letting $\psi_{B}=\varphi_{B}$ and then extending $\psi$ to a
Lipschitz map from $X$ to $\ell_{2}^{b}$; we use Lemmas 2.4 and 2.5 to show
that the extension exists. Similarly to $\psi_{B}$, we construct a map
$\psi_{A}$ that is Lipschitz on $X$ and bi-Lipschitz on $A$. Then we consider
the direct sum $\psi_{A}\oplus\psi_{B}$. This map is Lipschitz on $X$ and bi-
Lipschitz on $A$ and on $B$; however, it is not necessarily a bi-Lipschitz
embedding of $X$ since it may significantly decrease distances between points
in $A$ and $B$. Finally, we consider a map $\psi_{\Delta}:X\to{\mathbb{R}}$,
which, loosely speaking, preserves distances between points in $A$ and $B$,
and obtain a desired embedding
$\Psi=\psi_{A}\oplus\psi_{B}\oplus\psi_{\Delta}$.

######  Definition 2.1.

For a point $x$ in a metric space $(X,d)$ and a radius $r\geq 0$, we denote
the ball of radius $r$ around $x$ by
$\operatorname{Ball}_{r}(x)=\left\\{y:d(x,y)\leq r\right\\}$.

######  Definition 2.2.

For every $a\in A$, define $R_{a}=d(a,B)$; for every $b\in B$, define
$R_{b}=d(b,A)$, where $d(a,B)$ and $d(b,A)$ denote the distances from $a$ to
the set $B$ and from $b$ to the set $A$, respectively.

######  Definition 2.3.

Let $\alpha>0$. We say that $A^{\prime}\subset A$ is an $\alpha$-cover for $A$
with respect to $B$ if it satisfies the following two properties.

  1. 1.

For every $a\in A$, there is $a^{\prime}\in A^{\prime}$ such that
$R_{a^{\prime}}\leq R_{a}$ and $d(a,a^{\prime})\leq\alpha R_{a}$.

  2. 2.

For every distinct $a_{1}^{\prime},a_{2}^{\prime}\in A^{\prime}$, we have
$d(a_{1}^{\prime},a_{2}^{\prime})\geq\alpha\min(R_{a_{1}^{\prime}},R_{a_{2}^{\prime}})$.

######  Lemma 2.4.

Assume that $X=A\cup B$ is a finite metric space. For every $\alpha>0$, there
exists an $\alpha$-cover $A^{\prime}$ for $A$ with respect to $B$.

###### Proof.

We prove the lemma by induction on the size of $A$. If $A=\varnothing$, we let
$A^{\prime}=\varnothing$; then $A^{\prime}$ satisfies conditions (1) and (2).
Assume now that the statement of the lemma holds if $|A|<k$ (for some $k\geq
1$). We prove that it holds if $|A|=k$. Find a point $u$ in $A$ with the
smallest value of $R_{u}$; that is, a point $u\in A$ closest to $B$. Let
$Z=A\setminus\operatorname{Ball}_{\alpha R_{u}}(u)$. Note that $|Z|<|A|=k$. By
the induction hypothesis, the statement of the lemma holds for $Z$. Let
$Z^{\prime}$ be an $\alpha$-cover for $Z$ with respect to $B$, and
$A^{\prime}=Z^{\prime}\cup\left\\{u\right\\}$. We claim that $A^{\prime}$ is
an $\alpha$-cover for $A$ w.r.t. $B$. We verify that $A^{\prime}$ satisfies
properties (1) and (2) of an $\alpha$-cover.

1\. Let $a$ be a vertex in $A$. Consider two possibilities. Assume first that
$a\in\operatorname{Ball}_{\alpha R_{u}}(u)$. Then let $a^{\prime}=u$. By our
choice of $u$, $R_{a^{\prime}}\leq R_{a}$. Since
$a\in\operatorname{Ball}_{\alpha R_{u}}(u)$, we also have
$d(a,a^{\prime})=d(a,u)\leq\alpha R_{a}$. Thus, property (1) holds.

Assume now that $a\notin\operatorname{Ball}_{\alpha R_{u}}(u)$. Then $a\in Z$.
By the induction hypothesis, there exists $a^{\prime}\in Z^{\prime}\subset
A^{\prime}$ such that $R_{a^{\prime}}\leq R_{a}$ and
$d(a,a^{\prime})\leq\alpha R_{a}$, as required.

2\. Consider $a_{1}^{\prime},a_{2}^{\prime}\in A^{\prime}$. If both
$a_{1}^{\prime}$ and $a_{2}^{\prime}$ are in $Z^{\prime}$, then
$d(a_{1}^{\prime},a_{2}^{\prime})\geq\alpha\min(R_{a_{1}^{\prime}},R_{a_{2}^{\prime}})$
by the induction hypothesis. So let us assume that either $a_{1}^{\prime}$ or
$a_{2}^{\prime}$ is not in $Z^{\prime}$. That is, $a_{1}^{\prime}=u$ or
$a_{2}^{\prime}=u$. Without loss of generality, we assume that
$a_{1}^{\prime}=u$ and $a_{2}^{\prime}\in Z^{\prime}$. Since
$a_{2}^{\prime}\in Z^{\prime}\subset Z$, we have
$a_{2}^{\prime}\notin\operatorname{Ball}_{\alpha R_{u}}(u)$. Hence,
$d(a_{1}^{\prime},a_{2}^{\prime})\geq\alpha R_{u}=\alpha
R_{a_{1}^{\prime}}\geq\alpha\min(R_{a_{1}^{\prime}},R_{a_{2}^{\prime}})$. ∎

Let $A^{\prime}$ be an $\alpha$-cover. Consider a map $f:A^{\prime}\to B$ that
maps every point $a^{\prime}\in A^{\prime}$ to a point in $B$ closest to
$a^{\prime}$ (we break ties arbitrarily). That is, $f(a^{\prime})$ is such
that

$d(a^{\prime},f(a^{\prime}))=d(a^{\prime},B)=R_{a^{\prime}}.$

We show that $f$ is a Lipschitz map.

######  Lemma 2.5.

We have, $\|f\|_{Lip}\leq 2(1+1/\alpha)$.

###### Proof.

Let $a_{1}^{\prime}$ and $a_{2}^{\prime}$ be two points in $A^{\prime}$.

$\displaystyle d(f(a_{1}^{\prime}),f(a_{2}^{\prime}))$ $\displaystyle\leq
d(f(a_{1}^{\prime}),a_{1}^{\prime})+d(a_{1}^{\prime},a_{2}^{\prime})+d(a_{2}^{\prime},f(a_{2}^{\prime}))=R_{a_{1}^{\prime}}+R_{a_{2}^{\prime}}+d(a_{1}^{\prime},a_{2}^{\prime})$
$\displaystyle=2\min(R_{a_{1}^{\prime}},R_{a_{2}^{\prime}})+|R_{a_{1}^{\prime}}-R_{a_{2}^{\prime}}|+d(a_{1}^{\prime},a_{2}^{\prime}).$

Note that $\min(R_{a_{1}^{\prime}},R_{a_{2}^{\prime}})\leq
d(a_{1}^{\prime},a_{2}^{\prime})/\alpha$ by property 2 of an $\alpha$-cover,
and
$|R_{a_{1}^{\prime}}-R_{a_{2}^{\prime}}|=|d(a_{1}^{\prime},B)-d(a_{2}^{\prime},B)|\leq
d(a_{1}^{\prime},a_{2}^{\prime})$. Therefore,

$d(f(a_{1}^{\prime}),f(a_{2}^{\prime}))\leq
2d(a_{1}^{\prime},a_{2}^{\prime})/\alpha+d(a_{1}^{\prime},a_{2}^{\prime})+d(a_{1}^{\prime},a_{2}^{\prime})=2(1+1/\alpha)\cdot
d(a_{1}^{\prime},a_{2}^{\prime}).$

∎

By combining the maps $f$ and $\varphi_{B}$ we can obtain a
$2(1+1/\alpha)D_{B}$-Lipschitz embedding of $A^{\prime}$ to $\ell_{2}^{b}$. We
now show how to extend this embedding to the entire set $X$.

######  Lemma 2.6.

Assume that $X$ is finite. There exists a map $\psi:X\to\ell_{2}^{b}$ such
that

  1. 1.

For every $a_{1},a_{2}\in A$,

$\|\psi(a_{1})-\psi(a_{2})\|\leq 2(1+1/\alpha)D_{A}D_{B}d(a_{1},a_{2}).$ (1)

  2. 2.

For every $b_{1},b_{2}\in B$,

$d(b_{1},b_{2})\leq\|\psi(b_{1})-\psi(b_{2})\|=\|\varphi_{B}(b_{1})-\varphi_{B}(b_{2})\|\leq
D_{B}d(b_{1},b_{2}).$ (2)

  3. 3.

For every $a\in A$ and $b\in B$,

$d(a,b)-(1+\alpha)(2D_{A}D_{B}+1)R_{a}\leq\|\psi(a)-\psi(b)\|\leq(2(1+\alpha)D_{A}D_{B}+(2+\alpha)D_{B})d(a,b).$

###### Proof.

$\textstyle{A\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{A}}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces
A^{\prime}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\subset}$$\scriptstyle{\varphi_{A}}$$\scriptstyle{f}$$\textstyle{B\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\varphi_{B}}$$\textstyle{\varphi_{A}(A)\subset\ell_{2}^{a}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\tilde{g}}$$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces\varphi_{A}(A^{\prime})\subset\ell_{2}^{a}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\subset}$$\scriptstyle{g=\varphi_{B}^{\vphantom{-1}}f\varphi_{A}^{-1}}$$\textstyle{\ell_{2}^{b}}$
Figure 2: Commutative diagram for maps $g$ and $\tilde{g}$.

Consider map $g=\varphi_{B}^{\vphantom{-1}}f\varphi_{A}^{-1}$ from
$\varphi_{A}(A^{\prime})$ to $\varphi_{B}(B)\subset\ell_{2}^{b}$ (see Figure
2). We upper bound the Lipschitz norm of $g$ (using Lemma 2.5)

$\|g\|_{Lip}\leq\|\varphi_{B}\|_{Lip}\|f\|_{Lip}\|\varphi_{A}^{-1}\|_{Lip}\leq
D_{B}\cdot 2(1+1/\alpha)\cdot 1.$

By the Kirszbraun theorem, there is an extension
$\tilde{g}:\ell_{2}^{a}\to\ell_{2}^{b}$ of $g$ to $\ell_{2}^{a}$ with
$\|\tilde{g}\|_{Lip}=\|g\|_{Lip}\leq 2(1+\alpha)D_{B}/{\alpha}$. Define map
$\psi:X\to\ell_{2}^{b}$ as follows:

$\psi(x)=\begin{cases}\tilde{g}(\varphi_{A}(x)),&\text{if }x\in A,\\\
\varphi_{B}(x),&\text{if }x\in B.\end{cases}$

Note that if $x\in A\cap B$ then $x$ must be in $A^{\prime}$ and thus
$f(x)=x$. Therefore, both formulas for $\psi(x)$, $\tilde{g}(\varphi_{A}(x))$
and $\varphi_{B}(x)$, are equal, and $\psi(x)$ is well defined. We prove that
the map $\psi$ satisfies the conditions of the lemma.

1\. Consider $a_{1},a_{2}\in A$. We have,

$\|\psi(a_{1})-\psi(a_{2})\|=\|\tilde{g}(\varphi_{A}(a_{1}))-\tilde{g}(\varphi_{A}(a_{2}))\|\leq\|\tilde{g}\|_{Lip}\|\varphi_{A}\|_{Lip}\,d(a_{1},a_{2})\leq
2(1+1/\alpha)D_{A}D_{B}\cdot d(a_{1},a_{2}).$

2\. Consider $b_{1},b_{2}\in B$. By the definition of $\psi$,
$\|\psi(b_{1})-\psi(b_{2})\|=\|\varphi_{B}(b_{1})-\varphi_{B}(b_{2})\|$. Since
$\varphi_{B}$ is a non-expanding map with Lipschitz constant $D_{B}$, we have

$d(b_{1},b_{2})\leq\|\psi(b_{1})-\psi(b_{2})\|\leq D_{B}d(b_{1},b_{2}).$

3\. Finally, consider $a\in A$ and $b\in B$. By property 1 of an
$\alpha$-cover, there is an $a^{\prime}$ in $A^{\prime}$ such that
$R_{a^{\prime}}\leq R_{a}$ and $d(a,a^{\prime})\leq\alpha R_{a}$. Let
$b^{\prime}=f(a^{\prime})$. Note that
$d(a^{\prime},b^{\prime})=R_{a^{\prime}}\leq R_{a}$ and
$\psi(a^{\prime})=\varphi_{B}(f(a^{\prime}))=\psi(b^{\prime})$. We have,

$\|\psi(a)-\psi(b)\|\leq\|\psi(a)-\psi(a^{\prime})\|+\|\psi(a^{\prime})-\psi(b^{\prime})\|+\|\psi(b^{\prime})-\psi(b)\|=\|\psi(a)-\psi(a^{\prime})\|+\|\psi(b^{\prime})-\psi(b)\|.$

Plugging in upper bounds (1) and (2) for $\|\psi(a)-\psi(a^{\prime})\|$ and
$\|\psi(b)-\psi(b^{\prime})\|$, we get

$\|\psi(a)-\psi(b)\|\leq
2(1+1/\alpha)D_{A}D_{B}d(a,a^{\prime})+D_{B}d(b,b^{\prime}).$ (3)

We now upper bound $d(a,a^{\prime})$ and $d(b,b^{\prime})$. Note that
$R_{a}=d(a,B)\leq d(a,b)$. Thus

$d(a,a^{\prime})\leq\alpha R_{a}\leq\alpha d(a,b),$ (4)

and

$d(b,b^{\prime})\leq d(b,a)+d(a,a^{\prime})+d(a^{\prime},b^{\prime})\leq
d(a,b)+\alpha d(a,b)+R_{a}\leq(2+\alpha)d(a,b).$

From (3), we get

$\|\psi(a)-\psi(b)\|\leq\bigl{(}2(1+\alpha)D_{A}D_{B}+(2+\alpha)D_{B}\bigr{)}d(a,b)$

On the other hand, we have

$\|\psi(a)-\psi(b)\|\geq\|\psi(b)-\psi(b^{\prime})\|-\|\psi(a^{\prime})-\psi(b^{\prime})\|-\|\psi(a^{\prime})-\psi(a)\|\geq
d(b,b^{\prime})-0-2(1+\alpha)D_{A}D_{B}R_{a}.$

Here we used that $\psi(a^{\prime})=\psi(b^{\prime})$; we upper bounded
$\|\psi(a^{\prime})-\psi(a)\|$ using (1) and the first inequality in (4). We
bound $d(b,b^{\prime})$ as follows:

$d(b,b^{\prime})\geq d(a,b)-d(a,a^{\prime})-d(a^{\prime},b^{\prime})\geq
d(a,b)-\alpha R_{a}-R_{a^{\prime}}\geq d(a,b)-(\alpha+1)R_{a}.$

We get,

$\|\psi(a)-\psi(b)\|\geq d(a,b)-(1+\alpha)(2D_{A}D_{B}+1)R_{a}.$

This concludes the proof of Lemma 2.6. ∎

We are ready to prove Theorem 1.1.

######  Theorem 2.7 (Theorem 1.1 restated).

Consider a metric spaces $(X,d)$. Assume that $X$ is the union of two metric
subspaces $A$ and $B$ that embed into $\ell_{2}^{a}$ and $\ell_{2}^{b}$ with
distortions $D_{A}$ and $D_{B}$, respectively. Then $X$ embeds into
$\ell_{2}^{a+b+1}$ with distortion at most

$7D_{A}D_{B}+2(D_{A}+D_{B}).$

If $D_{A}=D_{B}=1$, then $X$ embeds into $\ell_{2}^{a+b+1}$ with distortion at
most $8.93$.

Furthermore, for given non-contracting embeddings
$\varphi_{A}:A\hookrightarrow\ell_{2}^{a}$ and
$\varphi_{B}:B\hookrightarrow\ell_{2}^{b}$ with $\|\varphi_{A}\|_{Lip}\leq
D_{A}$ and $\|\varphi_{B}\|_{Lip}\leq D_{B}$, there is a non-contracting
embedding $\Psi:X\hookrightarrow\ell_{2}^{a+b+1}$ with distortion at most
$7D_{A}D_{B}+2(D_{A}+D_{B})$ such that
$\|\Psi(u)-\Psi(v)\|\geq\|\varphi_{A}(u)-\varphi_{A}(v)\|$ for $u,v\in A$ and
$\|\Psi(u)-\Psi(v)\|\geq\|\varphi_{B}(u)-\varphi_{B}(v)\|$ for $u,v\in B$.

In this theorem, $a$ and $b$ may be finite or infinite.

###### Proof.

As we noted above, it is sufficient to prove the statement only for finite
sets $X$; see Lemma 2.9 for details. So we assume that $X$ is finite.

We let $\alpha=1/2$ in the proof of the bound $7D_{A}D_{B}+2(D_{A}+D_{B})$ on
the distortion, which holds for every $D_{A}$ and $D_{B}$; we let
$\alpha=0.3114$ in the proof of a tighter bound of 8.93, which holds for
$D_{A}=D_{B}=1$.

We construct a map $\psi:X\to\ell_{2}^{b}$ as in Lemma 2.6. Denote
$\psi_{B}=\psi$. Similarly (switching $A$ with $B$ in the statement of Lemma
2.6), we construct a map $\psi_{A}:X\to\ell_{2}^{a}$.

Let $\beta=(1+\alpha)(2D_{A}D_{B}+1)$ and $\gamma=\sqrt{1/2}\,\beta$. Define a
map $\psi_{\Delta}:X\to\mathbb{R}$ by $\psi_{\Delta}(a)=\gamma R_{a}$ for
$a\in A$ and $\psi_{\Delta}(b)=-\gamma R_{b}$ for $b\in B$. Finally, define an
embedding $\Psi:X\to\ell_{2}^{a+b+1}$:

$\Psi(x)=\psi_{A}(x)\oplus\psi_{B}(x)\oplus\psi_{\Delta}(x)\in\ell_{2}^{a+b+1}.$

First, we show that $\Psi$ is a non-contracting map. For $a_{1},a_{2}\in A$,

$\|\Psi(a_{1})-\Psi(a_{2})\|\geq\|\psi_{A}(a_{1})-\psi_{A}(a_{2})\|\stackrel{{\scriptstyle\text{\tiny
by (\ref{eq:psi-b-b})}}}{{\geq}}d(a_{1},a_{2}).$

Similarly, for $b_{1},b_{2}\in B$, $\|\Psi(b_{1})-\Psi(b_{2})\|\geq
d(b_{1},b_{2})$. For $a\in A$ and $b\in B$, we have

$\|\Psi(a)-\Psi(b)\|^{2}=\|\psi_{A}(a)-\psi_{A}(b)\|^{2}+\|\psi_{B}(a)-\psi_{B}(b)\|^{2}+\|\psi_{\Delta}(a)-\psi_{\Delta}(b)\|^{2}.$

By Lemma 2.6, item 3, and the definition of $\psi_{\Delta}$,

$\displaystyle\|\psi_{A}(a)-\psi_{A}(b)\|$ $\displaystyle\geq d(a,b)-\beta
R_{b},$ $\displaystyle\|\psi_{B}(a)-\psi_{B}(b)\|$ $\displaystyle\geq
d(a,b)-\beta R_{a},$ $\displaystyle\|\psi_{\Delta}(a)-\psi_{\Delta}(b)\|$
$\displaystyle=\gamma(R_{a}+R_{b}).$

By a simple case analysis, we show that these bounds imply that
$\|\psi(a)-\psi(b)\|\geq d(a,b)$.

######  Claim 2.8.

$\|\psi(a)-\psi(b)\|\geq d(a,b).$

###### Proof.

We assume without loss of generality that $R_{a}\leq R_{b}$. Consider three
cases. Assume first that $\beta R_{b}\leq d(a,b)$. Then

$\displaystyle\|\psi(a)-\psi(b)\|^{2}$ $\displaystyle\geq(d(a,b)-\beta
R_{a})^{2}+(d(a,b)-\beta R_{b})^{2}+\beta^{2}(R_{a}+R_{b})^{2}/2$
$\displaystyle=d(a,b)^{2}+(d(a,b)-\beta R_{a}-\beta
R_{b})^{2}+\beta^{2}(R_{a}-R_{b})^{2}/2\geq d(a,b)^{2}.$

Assume now that $\beta R_{a}\leq d(a,b)\leq\beta R_{b}$. Then

$\displaystyle\|\psi(a)-\psi(b)\|^{2}$ $\displaystyle\geq(d(a,b)-\beta
R_{a})^{2}+\beta^{2}(R_{a}+R_{b})^{2}/2$ $\displaystyle=d(a,b)^{2}-2\beta
d(a,b)R_{a}+\beta^{2}(3R_{a}^{2}+2R_{a}R_{b}+R_{b}^{2})/2$ $\displaystyle\geq
d(a,b)^{2}-2\beta^{2}R_{a}R_{b}+\beta^{2}(3R_{a}^{2}+2R_{a}R_{b}+R_{b}^{2})/2$
$\displaystyle=d(a,b)^{2}+\beta^{2}((\sqrt{3}R_{a}-R_{b})^{2}+2(\sqrt{3}-1)R_{a}R_{b})/2\geq
d(a,b)^{2}.$

Finally, assume that $d(a,b)\leq\beta R_{a}$. Then

$\|\psi(a)-\psi(b)\|^{2}\geq\beta^{2}(R_{a}+R_{b})^{2}/2\geq
2\beta^{2}R_{a}^{2}\geq 2d(a,b)^{2}.$

∎

We conclude that $\Psi$ is a non-contracting map. We now upper bound the
Lipschitz constant of $\Psi$. For $a_{1},a_{2}\in A$, we have

$\displaystyle\|\Psi(a_{1})-\Psi(a_{2})\|^{2}$
$\displaystyle=\|\psi_{A}(a_{1})-\psi_{A}(a_{2})\|^{2}+\|\psi_{B}(a_{1})-\psi_{B}(a_{2})\|^{2}+\|\psi_{\Delta}(a_{1})-\psi_{\Delta}(a_{2})\|^{2}$
$\displaystyle\leq(D_{A}^{2}+4(1+1/\alpha)^{2}D_{A}^{2}D_{B}^{2})d(a_{1},a_{2})^{2}+\gamma^{2}(R_{a_{1}}-R_{a_{2}})^{2}$
$\displaystyle\leq(D_{A}^{2}+4(1+1/\alpha)^{2}D_{A}^{2}D_{B}^{2}+\gamma^{2})d(a_{1},a_{2})^{2},$

here, we used that $|R_{a_{1}}-R_{a_{2}}|\leq d(a_{1},a_{2})$. Similarly, for
$b_{1},b_{2}\in B$, we have

$\|\Psi(b_{1})-\Psi(b_{2})\|^{2}\leq(D_{B}^{2}+4(1+1/\alpha)^{2}D_{A}^{2}D_{B}^{2}+\gamma^{2})d(b_{1},b_{2})^{2}.$

Now consider $a\in A$ and $b\in B$. Denote
$\xi_{A}=2(1+\alpha)D_{A}D_{B}+(2+\alpha)D_{A}$ and
$\xi_{B}=2(1+\alpha)D_{A}D_{B}+(2+\alpha)D_{B}$. We have,

$\displaystyle\|\Psi(a)-\Psi(b)\|^{2}$
$\displaystyle\leq\|\psi_{A}(a)-\psi_{A}(b)\|^{2}+\|\psi_{B}(a)-\psi_{B}(b)\|^{2}+\|\psi_{\Delta}(a)-\psi_{\Delta}(b)\|^{2}$
$\displaystyle\leq(\xi_{A}^{2}+\xi_{B}^{2})d(a,b)^{2}+\gamma^{2}(R_{a}+R_{b})^{2}\leq(\xi_{A}^{2}+\xi_{B}^{2}+4\gamma^{2}\bigr{)}d(a,b)^{2},$

here, we used that $R_{a}\leq d(a,b)$ and $R_{b}\leq d(a,b)$.

We first derive an upper bound for the Lipschitz constant of $\Psi$ in the
general case (for arbitrary $D_{A}$ and $D_{B}$). We plug in $\alpha=1/2$
(this value of $\alpha$ is suboptimal, but we use it to simplify the
calculations), and get

$\displaystyle\gamma^{2}$ $\displaystyle=\frac{9}{8}(2D_{A}D_{B}+1)^{2},$
$\displaystyle\frac{\|\Psi(a_{1})-\Psi(a_{2})\|^{2}}{d(a_{1},a_{2})^{{2}}}$
$\displaystyle\leq\frac{81}{2}D_{A}^{2}D_{B}^{2}+\frac{9}{2}D_{A}D_{B}+D_{A}^{2}+\frac{9}{8}\leq(7D_{A}D_{B}+2D_{A}+2D_{B})^{2},$
$\displaystyle\frac{\|\Psi(b_{1})-\Psi(b_{2})\|^{2}}{d(b_{1},b_{2})^{{2}}}$
$\displaystyle\leq(7D_{A}D_{B}+2D_{A}+2D_{B})^{2},$
$\displaystyle\frac{\|\Psi(a)-\Psi(b)\|^{2}}{d(a,b)^{{2}}}$ $\displaystyle\leq
36D_{A}^{2}D_{B}^{2}+15(D_{A}+D_{B})D_{A}D_{B}+\frac{25}{4}(D_{A}^{2}+D_{B}^{2})+18D_{A}D_{B}+\frac{9}{2}$
$\displaystyle\leq
36D_{A}^{2}D_{B}^{2}+15(D_{A}+D_{B})D_{A}D_{B}+\frac{25}{4}(D_{A}^{2}+D_{B}^{2})+18D_{A}D_{B}+\frac{9}{2}$
$\displaystyle\
{}{}+\left(13(D_{A}^{2}D_{B}^{2}+D_{A}^{2}D_{B}+D_{B}^{2}D_{A})-\frac{9}{4}(D_{A}^{2}+D_{B}^{2})-10D_{A}D_{B}-\frac{9}{2}\right)$
$\displaystyle=(7D_{A}D_{B}+2D_{A}+2D_{B})^{2}.$

We get that the Lipschitz constant of $\Psi$ is at most
$7D_{A}D_{B}+2(D_{A}+D_{B})$. Since $\Psi$ is non-contracting, the distortion
of $\Psi$ is at most $7D_{A}D_{B}+2(D_{A}+D_{B})$.

Now consider the special case $D_{A}=D_{B}=1$. Let $\alpha=0.3114$.

$\displaystyle\gamma^{2}$ $\displaystyle=\frac{9(1+\alpha)^{2}}{2},$
$\displaystyle\frac{\|\Psi(a_{1})-\Psi(a_{2})\|^{2}}{d(a_{1},a_{2})^{2}}$
$\displaystyle\leq
1+4(1+1/\alpha)^{2}+\frac{9(1+\alpha)^{2}}{2}<79.7<8.93^{2},$
$\displaystyle\frac{\|\Psi(b_{1})-\Psi(b_{2})\|^{2}}{d(b_{1},b_{2})^{2}}$
$\displaystyle\leq
1+4(1+1/\alpha)^{2}+\frac{9(1+\alpha)^{2}}{2}<79.7<8.93^{2},$
$\displaystyle\frac{\|\Psi(a)-\Psi(b)\|^{2}}{d(a,b)^{2}}$ $\displaystyle\leq
2(2+\alpha+2(1+\alpha))^{2}+18(1+\alpha)^{2}<79.7<8.93^{2}.$

We get that the distortion of $\Psi$ is less than $8.93$. ∎

###  2.1 Compactness argument

In this section, we prove that it is sufficient to prove Theorem 2.7 only for
finite metric spaces.

######  Lemma 2.9.

I. Let $(X,d)$ be a separable metric space. Assume that every finite subset of
$X$ embeds into $V=\ell_{2}^{m}$ with distortion at most $D$ (where $m$ is
either finite or infinite). Then $(X,d)$ embeds into $\ell_{2}^{m}$ with
distortion at most $D$.

II. Furthermore, assume that $X=A\cup B$. Let $\alpha:A\times
A\to{\mathbb{R}}$ and $\beta:B\times B\to{\mathbb{R}}$ be continuous
functions. Assume that for every finite subset $Y$ of $X$ there is an non-
contracting embedding $f:Y\hookrightarrow V$ with $\|f\|_{Lip}\leq D$ such
that $\|f(x)-f(y)\|\leq\alpha(x,y)$ for every $x,y\in A\cap Y$ and
$\|f(x)-f(y)\|\leq\beta(x,y)$ for every $x,y\in B\cap Y$. Then there exists an
non-contracting embedding $f:X\hookrightarrow V$ with $\|f\|_{Lip}\leq D$ such
that $\|f(x)-f(y)\|\leq\alpha(x,y)$ for every $x,y\in A$ and
$\|f(x)-f(y)\|\leq\beta(x,y)$ for every $x,y\in B$.

###### Proof.

I. Let $x_{0},x_{1},\dots,x_{k},\dots$ be a dense sequence in $X$. Consider an
orthonormal basis $e_{1},\dots,e_{m}$ in $\ell_{2}^{m}$, if $m<\infty$, or
$e_{1},\dots,e_{k},\dots$ in $\ell_{2}^{\infty}$, if $m=\infty$. Let $V_{k}$
be the linear span of vectors $e_{1},\dots,e_{k}$ if $k\leq m$ and $V_{k}=V$
if $k>m$. In particular, let $V_{0}=\left\\{0\right\\}$.

By the condition of the lemma, for every $k$, there exists an embedding
$f_{k}$ of $\left\\{x_{0},\dots,x_{k}\right\\}$ to $V$ with distortion at most
$D$. We assume without loss of generality that

$d(x_{i},x_{j})\leq\|f_{k}(x_{i})-f_{k}(x_{j})\|\leq Dd(x_{i},x_{j}).$

Further, we assume that $f_{k}(x_{0})=0$. Applying the Gram–Schmidt process to
$f_{k}(x_{0}),\dots,f_{k}(x_{k})$, we get an isometry $T:V\to V$ such that
$Tf_{k}(x_{i})\in V_{i}$ for $i\in\left\\{0,\dots,k\right\\}$ (in particular,
$f_{k}(x_{0})=0$). Denote $f_{k}^{\prime}=Tf_{k}$. Additionally, extend
$f_{k}^{\prime}$ to $\left\\{x_{i}:0\leq i<\infty\right\\}$ by letting
$f_{k}^{\prime}(x_{i})=0$ for $i>k$.

Let $B_{i}=\left\\{x\in V_{i}:\|x\|\leq Dd(x_{i},x_{0})\right\\}$. Note that
$f_{k}^{\prime}(x_{i})\in B_{i}$ since either

  * •

$f_{k}^{\prime}(x_{i})=0\in B_{i}$, or

  * •

$\|f_{k}^{\prime}(x_{i})\|=\|f_{k}^{\prime}(x_{i})-f_{k}^{\prime}(x_{0})\|\leq
Dd(x_{i},x_{0})$ and $f_{k}^{\prime}(x_{i})\in V_{i}$, thus
$f_{k}^{\prime}(x_{i})\in B_{i}$.

Therefore, $f_{k}^{\prime}\in\prod_{i=0}^{\infty}B_{i}$. Since each set
$B_{i}$ is compact, the space $\prod_{i=0}^{\infty}B_{i}$ is compact; also,
the space is metrizable, since it is a countable product of metric spaces.
Therefore, the sequence $f_{1}^{\prime},\dots,f_{k}^{\prime},\dots$ has an
accumulation point. Denote it by $f$.

Since for every $i$ and $j$, and all sufficiently large $k$,
$d(x_{i},x_{j})\leq\|f_{k}^{\prime}(x_{i})-f_{k}^{\prime}(x_{j})\|\leq
Dd(x_{i},x_{j})$, we have that $d(x_{i},x_{j})\leq\|f(x_{i})-f(x_{j})\|\leq
Dd(x_{i},x_{j})$. We obtained a desired embedding $f$. Finally, we extend $f$
from $\left\\{x_{i}\right\\}$ to $X$ by continuity, and obtain an embedding of
$X$ to $V$ with distortion at most $D$.

II. We proceed as in item I, except that we choose sequence
$x_{0},x_{1},\dots,x_{k},\dots$ so that $\left\\{x_{i}\right\\}\cap A$ is
dense in $A$ and $\left\\{x_{i}\right\\}\cap B$ is dense in $B$. Then since
every function $f_{k}$ satisfies the additional requirements, we get by
continuity that $f$ also satisfies them. ∎

##  3 Lower bound on distortion

In this section, we prove Theorem 1.2. Before we proceed to the proof, recall
the definition and some properties of graph Laplacians. Consider a graph
$G=(V,E)$. The Laplacian ${\cal{L}}$ of $G$ is a matrix with entries

${\cal{L}}_{uv}=\begin{cases}\deg u,&\text{ if }u=v,\\\ -1,&\text{ if
}(u,v)\in E,\\\ 0,&\text{ otherwise.}\end{cases}$

We write $X\succeq Y$ for two symmetric $n\times n$ matrices $X$ and $Y$, if
$X-Y$ is positive semidefinite.

######  Lemma 3.1.

Let $G=(A\cup B,E)$ be a complete bipartite graph with parts $A$ and $B$ of
size $n$ each. There exists a partition of the set of edges $E$ into two
disjoint sets $E_{1}$ and $E_{2}$ such that

$\frac{1}{(1+\delta)}{\cal{L}}_{1}\preceq\frac{1}{2}{\cal{L}}\preceq(1+\delta){\cal{L}}_{1}\qquad\text{and}\qquad\frac{1}{(1+\delta)}{\cal{L}}_{2}\preceq\frac{1}{2}{\cal{L}}\preceq(1+\delta){\cal{L}}_{2},$

where $\delta=c/\sqrt{n}$ (for some absolute constant $c$), and ${\cal{L}}$,
${\cal{L}}_{1}$ and ${\cal{L}}_{2}$ are the Laplacians of $G$, $G_{1}=(A\cup
B,E_{1})$ and $G_{2}=(A\cup B,E_{2})$, respectively.

###### Proof.

Let $E_{1}$ be a random subset of $E$ chosen uniformly among all subsets of
$E$. Let $E_{2}=E\setminus E_{1}$. Then $G_{1}$ is a random bipartite
$G(n,n,1/2)$ graph. Thus
$(1+\delta)^{-1}{\cal{L}}_{1}\leq\frac{1}{2}{\cal{L}}\leq(1+\delta){\cal{L}}_{1}$
with probability at least $2/3$ (see [4]). Similarly, $G_{2}$ is a random
bipartite $G(n,n,1/2)$ graph, and
$(1+\delta)^{-1}{\cal{L}}_{2}\leq\frac{1}{2}{\cal{L}}\leq(1+\delta){\cal{L}}_{2}$
with probability at least $2/3$ ($G_{1}$ and $G_{2}$ are, of course, not
independent). Therefore, with probability at least $1/3$, $E_{1}$ and $E_{2}$
satisfy the conditions of the lemma. ∎

######  Lemma 3.2.

Let $G=(A\cup B,E)$, $E_{1}$ and $E_{2}$ be as in Lemma 3.1. Consider a map
$f:A\cup B\to\ell_{2}$. Then for $i\in\left\\{1,2\right\\}$

$\frac{1}{(1+\delta)^{2}}\,\mathbb{E}_{(u,v)\in
E}\left[\|f(u)-f(v)\|^{2}\right]\leq\mathbb{E}_{(u,v)\in
E_{i}}\left[\|f(u)-f(v)\|^{2}\right]\leq(1+\delta)^{2}\,\mathbb{E}_{(u,v)\in
E}\left[\|f(u)-f(v)\|^{2}\right]$

###### Proof.

Let $h:A\cup B\to\\{0,1\\}$ be a function equal to $0$ on $A$ and $1$ on $B$.
Then,

$|E_{i}|=\langle h,{\cal{L}}_{i}h\rangle\leq(1+\delta)\langle
h,{\cal{L}}h\rangle/2=(1+\delta)|E|/2.$

Let $f_{j}(u)$ be the $j$-th coordinate of $f(u)$ in some fixed orthonormal
basis. We have,

$\displaystyle\mathbb{E}_{(u,v)\in E_{i}}$
$\displaystyle\bigl{[}\|f(u)-f(v)\|^{2}\bigr{]}=\frac{1}{|E_{i}|}\sum_{(u,v)\in
E_{i}}{\|f(u)-f(v)\|^{2}}=\frac{1}{|E_{i}|}\sum_{j}\langle
f_{j},{\cal{L}}_{i}f_{j}\rangle$
$\displaystyle\geq\frac{2}{(1+\delta)|E|}\cdot\sum_{j}\langle
f_{j},\Bigl{(}\frac{1}{2(1+\delta)}{\cal{L}}\Bigr{)}f_{j}\rangle=\frac{1}{(1+\delta)^{2}}\cdot\frac{1}{|E|}\sum_{j}\langle
f_{j},{\cal{L}}f_{j}\rangle$
$\displaystyle=\frac{1}{(1+\delta)^{2}}\cdot\frac{\sum_{(u,v)\in
E}\|f(u)-f(v)\|^{2}}{|E|}=\frac{1}{(1+\delta)^{2}}\cdot\mathbb{E}_{(u,v)\in
E}\left[\|f(u)-f(v)\|^{2}\right].$

The proof of the other part of the inequality is analogous. ∎

Now we are ready to prove Theorem 1.2.

###### Proof of Theorem 1.2.

Assume that $\varepsilon<1$. Let $\delta=\varepsilon/6$. Choose $n$ so that
$c/\sqrt{n}<\delta$. Let $A$ and $B$ be two disjoint sets consisting of $n$
vertices each. Consider the complete bipartite graph $G=(A\cup B,E)$ with
parts $A$ and $B$. Partition all edges $E$ into two disjoint sets $E_{1}$ and
$E_{2}$ as in Lemma 3.1. Denote the Laplacians of $G=(A\cup B,E)$,
$G_{1}=(A\cup B,E_{1})$ and $G_{2}=(A\cup B,E_{2})$ by ${\cal{L}}$,
${\cal{L}}_{1}$ and ${\cal{L}}_{2}$, respectively.

Define a metric space on $X=A\cup B$ as follows

$d(u,v)=\begin{cases}0,&\text{if }u=v,\\\ 2,&\text{if }u\neq v\text{ and
either both }a,b\in A\text{ or both }u,v\in B,\\\ 1,&\text{if }(u,v)\in
E_{1},\\\ 3,&\text{if }(u,v)\in E_{2}.\end{cases}$

It is easy to see that $(X,d)$ is a metric space. Indeed, we have $d(u,v)\geq
0$; $d(u,v)=0$ if and only if $u=v$; $d(u,v)=d(v,u)$. Consider three distinct
vertices $u$, $v$, and $w$. If $u,w\in A$ or $u,w\in B$ then $d(u,w)=2=1+1\leq
d(u,v)+d(v,w)$. If $u\in A$ and $w\in B$ then either $d(u,v)=2$ or $d(v,w)=2$,
and, therefore, $d(u,w)\leq 3=1+2\leq d(u,v)+d(v,w)$.

Note that both metric spaces $(A,d)$ and $(B,d)$ are isometric to regular
simplices in $\mathbb{R}^{n-1}$; in particular, they embed isometrically in
$\mathbb{R}^{n-1}$. We now show that every embedding of $(X,d)$ into
$\ell_{2}$ has distortion at least $3-\varepsilon$. Consider an embedding $f$
of $(X,d)$ into $\ell_{2}$. Denote the distortion of $f$ by $D$. Then for some
$c>0$,

$\|f(u)-f(v)\|\leq cD\text{ for }(u,v)\in E_{1}\text{ and }\|f(u)-f(v)\|\geq
3c\text{ for }(u,v)\in E_{2}.$

Thus,

$\frac{\mathbb{E}_{(u,v)\in
E_{1}}\left[\|f(u)-f(v)\|^{2}\right]}{\mathbb{E}_{(u,v)\in
E_{2}}\left[\|f(u)-f(v)\|^{2}\right]}\leq\frac{D^{2}}{9}.$

On the other hand, by Lemma 3.2,

$\frac{\mathbb{E}_{(u,v)\in
E_{1}}\left[\|f(u)-f(v)\|^{2}\right]}{\mathbb{E}_{(u,v)\in
E_{2}}\left[\|f(u)-f(v)\|^{2}\right]}\geq\left(\frac{1}{1+\delta}\right)^{4}.$

Therefore, $D\geq 3/(1+\delta)^{2}\geq 3-\varepsilon$. ∎

##  4 Corollaries and extensions to Theorem 1.1

###  4.1 Bi-Lipschitz extension

In this section, we prove an “external” bi-Lipschitz extension theorem. Let
$A\subset\ell_{2}^{a}$, $B\subset\ell_{2}^{b}$, and $f$ be a Lipschitz map
from $A$ to $B$. The Kirszbraun theorem states that the map $f$ can be
extended to a Lipschitz map $\tilde{f}$ from $\ell_{2}^{a}$ to $\ell_{2}^{b}$.
Is there a counterpart of this theorem for bi-Lipschitz maps? Note that there
may be no bi-Lipschitz extension even for a map from a subset of $\mathbb{R}$
to a subset of $\mathbb{R}$. Consider, for instance, a bi-Lipschitz map $f$
from $\left\\{0,1,2\right\\}\subset{\mathbb{R}}$ to
$\left\\{0,1,2\right\\}\subset{\mathbb{R}}$ that maps $0$ to $0$, $1$ to $2$
and $2$ to $1$. There is no continuous injective extension of $f$ to
$\mathbb{R}$.

We prove, however, that there is an “external” extension of a bi-Lipschitz
map.

######  Definition 4.1.

Let $A\subset\ell_{2}^{a}$ and $B\subset\ell_{2}^{b}$. Let $f:A\to B$ be a bi-
Lipschitz map. We say that a pair of maps $f_{1}:\ell_{2}^{a}\to\ell_{2}$ and
$f_{2}:\ell_{2}^{b}\to\ell_{2}$ is an external extension of $f$ with
distortion $D$ if

  * •

$f_{1}$ and $f_{2}$ have distortion at most $D$.

  * •

for every $a\in A$, $f_{1}(a)=f_{2}(f(a))$.

######  Theorem 4.2 (External Bi-Lipschitz Extension Theorem).

Let $A\subset U=\ell_{2}^{a}$ and $B\subset V=\ell_{2}^{b}$. Let $f:A\to B$ be
a bi-Lipschitz map with distortion $D$. Then there exists an external
extension $(f_{1},f_{2})$ of $f$ with distortion at most $O(D)$.

###### Proof.

Without loss of generality, we may assume that $f$ is non-contracting and
$\|f\|_{Lip}\leq D$. We assume that $U$ and $V$ are disjoint (by replacing $V$
with an isometric copy of $V$ if necessary). We are now going to take the
union of $U$ and $V$, identify each point $a\in A$ with $f(a)\in B$, and
consider the shortest path metric on the obtained space. Formally, let
$X=(U\cup V)/\left\\{(a,b):b=f(a)\right\\}$ (the union of $U$ and $V$ with
each point $a\in A$ identified with $f(a)\in B$). Let $d$ be the shortest path
metric on $X$; specifically, define metric $d$ as follows.

  * •

For $u,v\in U$, let $d(u,v)=\|u-v\|$.

  * •

For $u\in U$ and $v\in V$, let $d(u,v)=\inf_{x\in A}(\|u-x\|+\|f(x)-v\|)$.

  * •

For $u,v\in V$, let

$\displaystyle d(u,v)$ $\displaystyle=\min(\|u-v\|,\inf_{w\in
A}(d(u,w)+d(w,v)))$ $\displaystyle=\min(\|u-v\|,\inf_{x,y\in
B}(\|u-x\|+\|f^{-1}(x)-f^{-1}(y)\|+\|y-v\|)).$

Note that the distance between identified points $a\in A$ and $f(a)\in B$ is
$0$. It is straightforward to check that $(X,d)$ is a metric space.

We bound the distortions $D_{A}$ and $D_{B}$ with which $(U,d)$ and $(V,d)$
embed into $\ell_{2}^{a}$ and $\ell_{2}^{b}$, respectively. Note that $(U,d)$
is isometric to $(\ell_{2}^{a},\|\cdot\|)$. So $D_{A}=1$. Now consider the
identity map $id$ from $(V,d)$ to $(\ell_{2}^{b},\|\cdot\|)$. Note that
$d(u,v)\leq\|u-v\|$ by the definition of $d$. So $id$ is non-contracting.
Additionally, either $d(u,v)=\|u-v\|$ or

$\displaystyle d(u,v)$ $\displaystyle=\inf_{x,y\in
B}\|u-x\|+\|f^{-1}(x)-f^{-1}(y)\|+\|y-v\|$ $\displaystyle\geq\inf_{x,y\in
B}\|u-x\|+\|x-y\|/D+\|y-v\|\geq\|u-v\|/D.$

So $\|id\|_{Lip}\leq D$.

We apply111We would get better parameters if we applied Lemma 2.6 directly;
however, for simplicity of exposition we use Theorem 2.7 here. Theorem 2.7 to
the metric space $X$ and get that $X$ embeds into $\ell_{2}$ with distortion
at most $9D+2$. Denote the restrictions of this embedding to $U$ and $V$ by
$f_{1}$ and $f_{2}$, correspondingly. We claim that $(f_{1},f_{2})$ is an
external extension of $f$ with distortion at most $D^{\prime}=9D+2$.

Indeed, for every $a\in A$, $f_{2}(f(a))=f_{1}(a)$ since we identified $a$ and
$f(a)$. Then $f_{1}$ has distortion at most $D^{\prime}$. For $f_{2}$, we have

$\displaystyle f_{2}(u,v)$ $\displaystyle\geq\|u-v\|$ (by the “furthermore”
clause in Theorem 2.7) $\displaystyle f_{2}(u,v)$ $\displaystyle\leq
D^{\prime}d(u,v)\leq D^{\prime}\,\|u-v\|$ (since $f_{2}$ has distortion at
most $D^{\prime}$ as a map from $(X,d)$ to $\ell_{2}$)

We conclude that $f_{2}$ has distortion at most $D^{\prime}$ as a map from $V$
to $\ell_{2}$. ∎

###  4.2 An analog of Theorem 1.1 for arbitrary normed spaces

Theorem 1.1 applies only to embeddings into Euclidean spaces: if $U$ and $V$
are Euclidean spaces, $A$ and $B$ embed into $U$ and $V$ with distortions
$D_{A}$ and $D_{B}$, then $X=A\cup B$ embeds into $U\oplus
V\oplus{\mathbb{R}}$ with distortion $O(D_{A}D_{B})$. However, observe that
the proof of Theorem 1.1 uses only once that $U$ and $V$ are Euclidean – when
it extends map $g$ to a map $\tilde{g}$ using the Kirszbraun theorem. In this
section, we note that it is possible to generalize Theorem 1.1 to arbitrary
normed spaces $U$ and $V$. Since spaces $U$ and $V$ do not necessarily satisfy
the Kirszbraun theorem, our bound on the distortion with which $X$ embeds into
$U\oplus V\oplus{\mathbb{R}}$ depends on the Lipschitz extension constant for
normed spaces $U$ and $V$.

######  Theorem 4.3.

Consider a metric spaces $(X,d)$. Assume that $X$ is the union of two finite
metric subspaces $A$ and $B$ that embed into normed spaces $U$ and $V$ with
distortions $D_{A}$ and $D_{B}$, respectively. Denote $E_{A}=e_{|A|}(A,V)$ and
$E_{B}=e_{|B|}(B,U)$ (see Section 1.1 for the definition of the Lipschitz
extension constants $e_{k}$). Then $X$ embeds into $U\oplus
V\oplus{\mathbb{R}}$ with distortion at most

$O(E_{A}D_{B}+D_{A}E_{B}).$

The proof of the theorem is almost identical to the proof of Theorem 1.1. The
only difference is that in the proof of Lemma 2.6, we define $\psi(x)$ for
$x\in A$ not as $\tilde{g}(\varphi_{A}(x))$ but rather as an extension of map
$\varphi_{B}f:A^{\prime}\to V$ from $A^{\prime}$ to $A$. Then
$\|\varphi_{B}f\|\leq D_{B}2(1+1/\alpha)$ and $\|\psi|_{A}\|_{Lip}\leq
2E_{A}D_{B}(1+1/\alpha)$.

Now we present a corollary of this theorem communicated to us by Naor.

######  Corollary 4.4 (Naor).

Consider a metric space $X=A\cup B$ on $n$ points. Assume that $A$ embeds
isometrically into normed space $U$ and $B$ into normed space $V$. Then $X$
embeds into $U\oplus V\oplus{\mathbb{R}}$ with distortion at most $O(\log
n/\log\log n)$.

###### Proof.

We apply Theorem 4.3. Note that $D_{A}=D_{B}=1$. As Lee and Naor [7] showed,
the Lipschitz extension constant $e_{k}(Y,W)=O(\log k/\log\log k)$ for every
metric space $Y$ and normed space $W$. Therefore, $E_{A}=O(\log n/\log\log n)$
and $E_{B}=O(\log n/\log\log n)$. The corollary follows. ∎

##  5 Open problems

In this section, we present several open problems.

######  Question 3.

Obtain tight or almost tight upper and lower bounds for ${\cal
D}(D_{A},D_{B})$. In particular, find the asymptotic behavior of ${\cal
D}(D,D)$ when $D\to\infty$. Currently, we only know that $\Omega(D)\leq{\cal
D}(D,D)\leq O(D^{2})$. We conjecture that ${\cal D}(D,D)=\Theta(D^{2})$.

######  Question 4.

We know that ${\cal D}(1,1)\in[3,8.93)$. What is the exact value of ${\cal
D}(1,1)$?

######  Question 5.

Study the problem for spaces $\ell_{p}$ with $p\neq 2$. Assume that $X=A\cup
B$, where $A$ and $B$ embed into $\ell_{p}$ isometrically. Is it true that $X$
embeds into $\ell_{p}$ with bounded distortion? We conjecture that the answer
is negative for every $p\notin\left\\{2,\infty\right\\}$.

######  Question 6.

Assume that $X=A_{1}\cup A_{2}\cup\dots\cup A_{k}$, and each $A_{i}$ embeds
isometrically into $\ell_{2}$. What is the smallest $D_{k}$ such that $X$
necessarily embeds into $\ell_{2}$ with distortion at most $D_{k}$. We can get
from Theorem 1.1 by induction on $k$ that $D_{k}\leq 2^{O(k)}$. On the other
hand, even if all sets $A_{1},\dots,A_{k}$ are singletons (and thus trivially
embed into $\ell_{2}$), $D_{k}\geq\Omega(\log k)$ [6, 9].

Finally, we want to reiterate that Question 2 is still open (see the
introduction). Currently known lower and upper bounds for $D_{n,k,p}$ do not
match. In particular, the following question is interesting.

######  Question 7.

What is the value of $D_{n,k,p}$ for $k=\sqrt{n}$ and $p=2$?

## Acknowledgements

We thank Assaf Naor for useful discussions. We thank Tommaso Goldhirsch and an
anonymous referee for their very valuable comments about the preliminary
version of this paper, and, in particular, for finding a typo in the statement
of Lemma 2.6, item 3, and pointing out that by fixing this typo, it is
possible to get a better bound on the distortion in the isometric case when
$D_{A}=D_{B}=1$.

## References

  * [1] S. Arora, L. Lovász, I. Newman, Y. Rabani, Y. Rabinovich, and S. Vempala.  Local versus global properties of metric spaces.  In Proc. of the Symposium on Discrete Algorithms, pp. 41–50, 2006.
  * [2] M. Charikar, K. Makarychev, and Y. Makarychev.  Local global tradeoffs in metric embeddings.  SIAM Journal on Computing 39, no. 6 (2010): 2487–2512.
  * [3] M. Charikar, K. Makarychev, and Y. Makarychev.  Integrality gaps for Sherali–Adams relaxations.  In Proc. of the Symposium on Theory of Computing, pp. 283–292, 2009.
  * [4] Z. Füredi and J. Komlós.  The eigenvalues of random symmetric matrices.  Combinatorica 1, no. 3 (1981): 233–241.
  * [5] M. Kirszbraun.  Über die zusammenziehende und Lipschitzsche Transformationen.  Fundamenta Mathematicae 22, no 1 (1934): 77–108.
  * [6] N. Linial, E. London, and Y. Rabinovich.  The geometry of graphs and some of its algorithmic applications.  Combinatorica 15, no. 2 (1995): 215–245.
  * [7] J. R. Lee and A. Naor.  Absolute Lipschitz extendability.  Comptes Rendus Mathematique 338, no. 11 (2004): 859–862.
  * [8] M. Mendel and A. Naor.  Ultrametric skeletons.  Proc. Natl. Acad. Sci. 110, no. 48 (2013): 19256–19262.
  * [9] M. I. Ostrovskii.  Metric embeddings: bilipschitz and coarse embeddings into Banach spaces.  Vol. 49. Walter de Gruyter, 2013.
  * [10] J. H. Wells and L. R. Williams.  Embeddings and extensions in analysis. Vol. 84. Springer Science & Business Media, 2012.

[konstantin] Konstantin Makarychev
Microsoft Research
Redmond, WA, USA
konstantin.makarychevgmailcom
http://konstantin.makarychev.net [yury] Yury Makarychev
Toyota Technological Institute at Chicago (TTIC)
Chicago, IL, USA
yurytticedu
http://ttic.uchicago.edu/~yury