Notes of Romain Tessera’s Rennes lecture nr 1

Relative expanders

1. Coarse embeddings into Hilbert spaces

In 1993, motivated by an approach suggested by Connes to Novikov conjecture, Gromov suggested to investigate coarse embeddings of groups in Hilbert space {\mathcal{H}}.

Definition 1 Let {X} be a metric space. A map {F:X\rightarrow\mathcal{H}} is a coarse embedding if distances in the range and in the domain tend to infinity simultaneously (each is bounded by a function of the other).

Question: does every separable metric space admit such embeddings ?

A counterexample was soon obtained. It is based on old work of Per Enflo. Since anay metric space embeds isometrically in some {L^{\infty}}, it is natural to look there for a counterexample.

Theorem 2 (Dranishnikov-Lafforgue-Yu) The sequence {X_n=(\ell_n^{\infty})} does not coarsely embed into {\mathcal{H}}.

Easy to discretize and organize into a graph. Drawback: degree of vertices is unbounded.

2. Expanders

In 2000, Gromov improved the example to get bounded degree graphs, using an expander.

Definition 3 An expander is a sequence of finite graphs {X_n} whose size tends to infinity, degree stays bounded, but Cheeger constant

\displaystyle  \begin{array}{rcl}  \inf \{\frac{|\partial A|}{|A|}\,;\, A\subset X_n,\,|A|\leq\frac{1}{2}|X_n]\} \end{array}

stays bounded below.

Example. Large squares do not form an expander. Indeed, cutting in half requires only linear boundary. Trees do not either: cutting one edge suffices to split in half.

So it is not that easy to produce examples of expanders. Until 2000, the only known sources were

  • Random graphs (Kolmogorov-Barzdin 1960’s, Pinsker 1973).
  • Group theory (Margulis 1973).

3. Expanders versus embeddings

An alternate characterization of expanders was given by N. Alon in 1986.

Theorem 4 (Alon) The sequence {X_n} is an expander iff it has a uniform spectral gap, i.e. for all {n} and for every real valued function {f} on {X_n},

\displaystyle  \begin{array}{rcl}  \frac{1}{|X_n|^2}\sum_{x,\,y\in X_n}|f(x)-f(y)|^2 \leq \frac{1}{\lambda}\frac{1}{|X_n|}\sum_{x\sim y\in X_n}|f(x)-f(y)|^2 . \end{array}

Corollary 5 An expander does not coarsely embed into {\mathcal{H}}.

Indeed, a coarse embedding {F:X_n\rightarrow\mathcal{H}} is {C}-Lipschitz. The spectral gap provides us with a point {x_0} such that

\displaystyle  \begin{array}{rcl}  \frac{1}{|X_n|}\sum_{x\in X_n}|F(x)-F(x_0)|^2 \leq C^2 d, \end{array}

where {d} is the degree. A positive proportion of points of {X_n} satisfy {|F(x)-F(x_0)|^2 \leq 2C^2 d}. But, under a coarse embedding, the size of the inverse image of balls of fixed radius is bounded, contradiction.

Corollary 6 A metric space that weakly contains an expander does not coarsely embed into {\mathcal{H}}.

Weakly contains means {j_n:X_n \rightarrow X} is {C}-Lipschitz and inverse images of points represent a decaying proportion of points of {X_n}.

Question. Conversely, if a bounded degree graph does not coarsely embed into {\mathcal{H}}, does it weakly contain an expander ?

4. Expanders from group theory

4.1. Property (T)

Definition 7 Let {G} be a finitely generated group. Say {G} has property (T) if every isometric affine action of {G} on a Hilbert space has bounded orbits ({\Leftrightarrow} has a fixed point).

Examples. Infinite solvable (more generally, amenable) groups are not (T). Free groups are not (T). Lattices in higher rank simple Lie groups, e.g. {SL(3,{\mathbb Z})}, are (T).

Pick a generating system {S} for {SL(3,{\mathbb Z})}. Take {X_n=Cay(Sl(3,{\mathbb Z}/n{\mathbb Z}),S)}. Then {X_n} get large and have degree bounded above by {2|S|}. I claim that {X_n} have a uniform spectral gap.

4.2. A lemma

Fact. Let {G} be a property (T) group with generating system {S}. There exists {C} such that for every unitary representation {\pi} and any cocycle {b},

\displaystyle  \begin{array}{rcl}  |b(g)|\leq C\,\max_{s\in S}|b(s)|. \end{array}

Proof is by contradiction. Otherwise, get sequence {b_n}, {\pi_n} with {|b_n|\leq 1} on {S} but {|b(g_n)|} tends to infinity. Form the {\ell^2} direct sum {\bigoplus_n \pi_n}, set {b=\sum_{n}b_n}. Then the corresponding affine isometric action has unbounded orbits.

4.3. Spectral gap for {G_n=Sl(3,{\mathbb Z}/n{\mathbb Z})}

View {\ell^2(G_n)}, with action on the right, as a unitary representation of {G=SL(3,{\mathbb Z})}. Take {\ell^2} direct sum. Define cocycle {b} by

\displaystyle  \begin{array}{rcl}  b_f(g)=f(\cdot g)-f=\pi(g)f-f \end{array}

for {f\in \bigoplus_n \ell^2(G_n)}. Then

\displaystyle  \begin{array}{rcl}  |b|_{\ell^2(G_n)}^2=\frac{1}{|X_n|}\sum_{x\in X_n}|f(x)|^2. \end{array}

Furthermore, previous lemma yields

\displaystyle  \begin{array}{rcl}  \frac{1}{|X_n|}\sum_{x\in X_n}|f(xg)-f(x)|^2\leq C\frac{1}{|X_n|}\sum_{x\in X_n}\sum_{s\in S}|f(xs)-f(x)|^2. \end{array}

Averaging over {g\in G_n} yields the spectral gap (also known as Poincaré) inequality.

Note that the same argument would apply to amenable quotients of {SL(3,{\mathbb Z})}, instead of finite ones.

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