** Expanders and separation **

How different can expanders be ?

**1. Expanders **

Definition 1An -expander is a sequence of finite graphs where – each has Cheeger constant .

A -expander is a sequence of finite graphs where – each has maximal degree , – each has Cheeger constant .

Margulis: Cayley graphs of finite quotients of (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 coarsely embeds in Hilbert space, then Novikov conjecture holds for all closed manifolds with fundamental group .

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 small cancellation labellings.

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

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

Theorem 2There exists a continuum of -expanders , real number, such that does not coarsely embed into unless .

Theorem 3There exists a continuum of finitely generated groups , real number, such that does not coarsely embed into unless .

**3. Separation **

To distinguish expanders, we use separation.

Definition 4 (Benjamini-Schramm-Timar)finite graph. The cut-size of is the smallest such that there exists a subset of vertices of size such that every connected component of the complement of in contains at most half of the vertices of .For an infinite graph , the separation profile is the function

Separation behaves rather differently from Cheeger constant.

Example 1 (Benjamini-Schramm-Timar)For bounded geometry graphs, let be Lipschitz and fibers have bounded size, then .

Proposition 5 (Benjamini-Schramm-Timar)

Theorem 6infinite graph. Then is not sublinear contains an -expander. If furthermore has bounded degree, then is not sublinear contains a -expander.

**4. Proof **

** 4.1. Characterization of expanders **

(i) If G is a finite graph with Cheeger constant , then . Indeed, let be a cut set for . A greedy search provides a collection of components of with size between and . Its boundary is contained in .

(ii) Conversely, let be a finite graph of size . There is a subgraph of size such that .

** 4.2. Different separation profiles **

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

- girth , –
- .

Observe that if , are infinite subsets of integers, with infinite, then is not bounded above by . 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.