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.

Advertisements

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 http://www.math.ens.fr/metric2011/
This entry was posted in seminar. Bookmark the permalink.

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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