Notes of Florent Baudier’s introductory lecture

Presentation of the Fall School on Metric Embeddings

1. Basics

Basic objects in this school are metric spaces. Here are a few definitions.

1.1. Classes of spaces

Proper: closed balls are compact.

Locally finite: every ball has at most finitely many points in it.

Bounded geometry (also known as uniformly locally finite): an upper bound on the number of points in a ball depends only on radius.

1.2. Examples

Graphs are equipped with the shortest path distance, where edges have length 1. In particular, Cayley graphs of finitely generated groups.

1.3. Maps

Given a map {f:X\rightarrow Y} between metric spaces, define the

Expansion modulus {\omega_f(t)=\sup\{d(f(x),f(x'))\,;\,d(x,x')\leq t\}}.

Compression modulus {\rho_f(t)=\inf\{d(f(x),f(x'))\,;\,d(x,x')\geq t\}}.

{f} is isometric iff {\rho_f=\omega_f}.

{f} is homothetic (people sometimes call this isometric as well) if {\rho_f=s\omega_f} for some constant {s>0}.

Example. A tripod cannot be isometrically embedded in Euclidean plane.

{f} is bi-Lipschitz if {\rho_f(t)\geq \frac{st}{B}}, {\omega_f(t)\leq sAt} for some constants {A}, {B}, {s>0}. When {Y} is a Banach space, one usually takes {s=B=1}.

{f} is a uniform embedding if {\rho_f>0} and {\omega_f(t)} tends to 0 as {t} tends to 0.

{f} is a coarse embedding if {\rho_f} and {\omega_f} are finite and {\rho_f(t)} tends to infinity as {t} tends to infinity.

{f} is a strong embedding if it is uniform and coarse.

Remark. Coarse does not imply continuous nor injective.

Example. The integer part function {{\mathbb R}\rightarrow{\mathbb Z}} is coarse.

{f} is quasi-isometric or coarse Lipschitz if {\rho_f(t)\geq \frac{t}{A}-B}, {\omega_f(t)\leq At+B} for some constants {A}, {B>0}.

Example 1 A subset {S} in a metric space {M} is an {\epsilon,\delta}-skeleton if pairwise distances in {S} are {\geq\epsilon} and every point of {M} sits at distance {\leq\delta} from {S}. When {\epsilon=\delta}, one speaks of an {\epsilon}-net. Then the nearest point map {M\rightarrow S} is quasisometric.

1.4. Corson-Klee Lemma

Say a metric space is metrically convex if for all {t\in[0,1]} and all points {x}, {x'}, there exists a point {z_t} such that

\displaystyle  \begin{array}{rcl}  d(z_t,x)=td(x,x'),\quad d(z_t,x')=(1-t)d(x,x'). \end{array}

Example. Graphs are metrically convex.

Lemma 1 Let {X} be metrically convex. Let {f:X\rightarrow Y} have {\omega_f(t_0)<+\infty} for some {t_0}. Then

\displaystyle  \begin{array}{rcl}  d(f(x),f(x'))\leq C(t_0)d(x,x')\quad \textrm{provided}\quad d(x,x')\geq t_0. \end{array}

2. Quantitative theory

We are interested in the optimal behaviour of expansion and compression moduli among all maps between specific metric spaces.

2.1. Distorsion

Denote by

\displaystyle  \begin{array}{rcl}  dist(f)=\sup\frac{d(f(x),f(x'))}{d(x,x')}\sup\frac{d(x,x')}{d(f(x),f(x'))}. \end{array}

The best distorsion of maps {X\rightarrow Y} is called the \textrm{{Y}-distorsion} of {X}.

2.2. Snowflaking exponent

When {s\in(0,1)}, raising a metric to the power {s} still gives a metric. This is the snowflaking operation.


\displaystyle  \begin{array}{rcl}  s_Y(X)=\sup\{s\in(0,1)\,;\,(X,d_X^s) \textrm{ has a bi-Lipschitz embedding into }Y\}. \end{array}

2.3. Compression exponent

Introduced by Guentner and Kaminker. Define

\displaystyle  \begin{array}{rcl}  \alpha_Y(X)=\sup\{\alpha\in(0,1)\,;\,\exists f:X\rightarrow Y\textrm{ such that }\omega_f(t)\leq At+B,\,\rho_f(t)\geq\frac{t^\alpha}{A}-B\}. \end{array}

No exponent {\alpha} on the right-hand side (i.e. for {\omega_f}), which makes it different from the snowflaking exponent. But {s\leq \alpha}.

3. Why do we care ?

Embedding a graph (network…) in a Banach space is a technique used in computer science

In geometric group theory, equivariant Hilbertian compression {>\frac{1}{2}} implies group is amenable.

In topology, coarse embeddability of the fundamental group into Hilbert space implies that Novikov’s conjecture holds for the space.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s