Expanders and separation
How different can expanders be ?
Definition 1 An -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 2 There exists a continuum of -expanders , real number, such that does not coarsely embed into unless .
Theorem 3 There exists a continuum of finitely generated groups , real number, such that does not coarsely embed into unless .
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 6 infinite graph. Then is not sublinear contains an -expander. If furthermore has bounded degree, then is not sublinear contains a -expander.
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.