Notes of David Hume’s Orsay lecture

Expanders and separation

How different can expanders be ?

1. Expanders

Definition 1 An {\epsilon}-expander is a sequence of finite graphs {G_n} where – each {G_n} has Cheeger constant {>\epsilon}.

A {(d,\epsilon)}-expander is a sequence of finite graphs {G_n} where – each {G_n} has maximal degree {< d}, – each {G_n} has Cheeger constant {>\epsilon}.

Margulis: Cayley graphs of finite quotients of {Sl(3,{\mathbb Z})} (or of any propertyT residually finite group) are an expander.

Lubotzky-Philipps-Sarnak, Lubotzky pursued the finite group line.

Wigderson : zig-zag construction of expanders.

2. Connection to Topology

Borel conjecture : given two closed aspherical manifolds, any homotopy equivalence is homotopic to a homeomorphism.

This is hard. An important related (philosophically weaker) question is the Novikov conjecture, which has partials solutions.

Yu : if a finitely generated group {G} coarsely embeds in Hilbert space, then Novikov conjecture holds for all closed manifolds with fundamental group {G}.

Since expanders do not coarsely embed into Hilbert space, Gromov asked wether there exist finitely generated groups that coarsely contain expanders.

Gromov (followed by Coulon and Arzhantseva-Delzant) provided a slightly weaker construction. This was made more precise by

Osajda : there exist expander families with {C'(1/6)} small cancellation labellings.

Idea : graphical small cancellation. Pick finite graphs {G_n} with oriented edges, labelled by a finite set S. Define

\displaystyle G_I=<S|\textrm{ all words read along oriented loops in each }G_n >.

Then graphical small cancellation theory gives sufficient conditions in order that the disjoint union of {G_n} embeds isometrically in {G}.

Theorem 2 There exists a continuum of {(d,\epsilon)}-expanders {G_r}, {r} real number, such that {G_r} does not coarsely embed into {G_s} unless {r=s}.

Theorem 3 There exists a continuum of finitely generated groups {G_r}, {r} real number, such that {G_r} does not coarsely embed into {G_s} unless {r=s}.

3. Separation

To distinguish expanders, we use separation.

Definition 4 (Benjamini-Schramm-Timar) {G} finite graph. The cut-size of {G} is the smallest {k} such that there exists a subset {A} of vertices of size {k} such that every connected component of the complement of {A} in {G} contains at most half of the vertices of {G}.

For an infinite graph {X}, the separation profile {sep_X} is the function

\displaystyle sep_X(n)= \max \{\textrm{cut-size of a subgraph of size } < n\}.

Separation behaves rather differently from Cheeger constant.

Example 1 (Benjamini-Schramm-Timar) For bounded geometry graphs, let {r : X\rightarrow Y} be Lipschitz and fibers have bounded size, then {sep_X < C sep_Y + C}.

Proposition 5 (Benjamini-Schramm-Timar)

\displaystyle  \begin{array}{rcl}  sep_{{\mathbb Z}^k} &=& n^{k-1/k} .\\ sep_{H^k} &=& \begin{cases} \log n & \text{ if }k=2, \\ n^{k-2/k-1}& \text{ if }k\geq 3. \end{cases}\\ sep_{F_k} &=& 1.\\ sep_{F_2\times F_2} &=&\frac{n}{\log n}. \end{array}

Theorem 6 {X} infinite graph. Then {sep_X} is not sublinear {\Leftrightarrow X} contains an {\epsilon}-expander. If furthermore {X} has bounded degree, then {sep_X} is not sublinear {\Leftrightarrow X} contains a {(d,\epsilon)}-expander.

4. Proof

4.1. Characterization of expanders

(i) If G is a finite graph with Cheeger constant {h > \epsilon}, then {cut(G) > n \epsilon/4}. Indeed, let {C} be a cut set for {G}. A greedy search provides a collection {D} of components of {G\setminus C} with size between {n/4} and {n/2}. Its boundary is contained in {C}.

(ii) Conversely, let {G} be a finite graph of size {n}. There is a subgraph {G'} of size {\geq n/2} such that {h(G')\geq cut(G)/2n}.

4.2. Different separation profiles

To construct expanders with different separation profiles that can be embedded into groups, pick a (d,{\epsilon})-expander ({G_n}) such that –

  1. girth {g(G_{n+1}) > 2 |G_n|}, –
  2. {|G_n| > 3 |G_{n-1}|}.

Observe that if {M}, {N} are infinite subsets of integers, with {M\setminus N} infinite, then {sep_{G_M}} is not bounded above by {sep_{G_N}}. Indeed, below girth, separation profile is dramatically low.

When embedded into groups, the receiving groups have a separation profile governed by the graph at certain scales, and are essentially hyperbolic at others. But hyperbolic implies polynomial separation profile.


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 seminar. 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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s