## 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=.$

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.