1. Consequences of the zig-zag product
- , escaping from every maze deterministically (Reingold).
- Superexpanders (Mendel, Naor)
- Connection with semi-direct products of groups (Alon, Lubotzky, Wigderson).
- New expanding Cayley graphs for non simple groups,
- Meshulam, Wigderson: Iterated group algebras.
- Rozenman, Shalev, Wigderson: Iterated wreath products.
- Beating eigenvalue bounds.
2. Expansion in near abelian groups
2.1. Iterated semi-direct products with group algebras
Theorem 1 (Lubotzky, Weiss) If is -step colvable and is expanding, then
This is essentially sharp, as we show with Meshulam. Start with and iterate semi-direct product .
Conjecture: If is expanding, then has at most irreducible representations of dimension .
[De la Harpe, Robertson, Valette]: True if is replaced with .
[Meshulam, Wigderson]: True with for monomial groups.
2.2. Iterated wreath products
Iterate . Then is the group of even automorphisms of a rooted depths tree.
Theorem 2 (Rozenman, Shalev, Wigderson) is expanding with explicit bounded number of generators.
3. Beating eigenvalue bounds
Task: Given , construct a low degree graph such that every two sets of size are connected by an edge.
Ramanujan graphs achieve .
Random graphs achieve .
Zig-zag graphs achieve .
Sorting and selection in rounds, superconcentrators.
3.2. Lossless expanders
Task: Construct a -regular gra ph in which every set of size has vertex expansion .
Ramanujan graphs achieve . [Kahale]
Note that is a key threshold for applications.
Random graphs achieve . These are called lossless expaders.
Zig-zag graphs achieve . [Capalbo, Reingold, vadhan, Wigderson].
Many applications, here is one.
4. Error correcting codes
Recall that a code is good if rate and normalized distance are bounded below.
Random codes are good [Shannon]. Challenge: find good, explicit and efficent codes.
Gallager introduced combinatorial constructions.
Spielman : Good, explicit codes with linear encoding and decoding times.
4.1. Graph-based codes (Gallager)
Start with a bipartite graph. Interpret left vertices as equations for a linear code. Encoding time is quadratic. If is lossless, then encoding time is linear.
theorem We can construct graphs with , right degree and suchthat any set of size has vertex expansion .
Sipser, Spielman:While , flip all with has more ‘s than ‘s
They show that the number of corrupted positions falls by a factor of at each flipping step.
5. Rapidly mixing Markov chains
We claim that expansion naturally arises in many (exponential graphs) from applications.
5.1. Volumes of convex bodies
[Dyer, Frieze, Kannan 1991]: Put a fine grid on the space. To approximately count grid points in , sample at random. This does not always work, but works in settings which are hereditary. This is the case here.
Random walk on the grid and reflect if leaving . The limiting distribution is uniform in . Need a spectral gap. This is equivalent to an isoperimetric inequality.
5.2. Statistical mechanics
Task: Count approximately the number of domino tilings in a region of the -dimensional grid.
Use Glauber dynamics, i.e. MCMC sampling the Gibbs distribution. For this, construct a graph with edges representing local changes. Then run a random walk
[Jerrum, Sinclair]: Polytime convergence for near-uniform perfect matchings, for the Ising model.
5.3. Generating random group elements
Task: Given a subset of a finite (matrix) group, sample (approximately) elements of the group generated by from the uniform distribution.
[Babai, Szemerédi] introduced the product replacement algorithm: change by changing generator into inverse or multiplying two generators.
Theorem 3 (Babai, Szemerédi) Every element is reached in time .
Theorem 4 (Cooperman, Dixon, Green) The procedure produces near random element in time .
Note this applies to arbitrary group. Local expansion suffices for the process to propagate fast. Nevertheless, proof uses techniques similar to those alluded to by Gamburd and Breuillard.
6. Extensions of expanders
6.1. Dimension expanders
Definition 5 (Barak, Impagliazzo, Shpilka, Wigderson) A set is a dimension expander if for every subspace of dimension , there exists such that
A bounded number of random linear maps does the job. [Lubotzky] gave an explicit construction in characteristic . [Dvir, Shpilka] could construct -dimension expanders in the general case using monotone expanders. This was improved to bounded size by [Bourgain], see Dvir’s talk.
7. Open problems
- Characterize which Cayley graphs are expanders. Connect with dimensions of irreducible representations ?
- Construct lossless bipartite expanders: every small set expands.
- Construct rate concentrators, i.e. very unbalanced bipartite expanders.