**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

with logs.

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 .

** 3.1. Applications **

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 .

Obviously .

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.

** 4.2. Decoding **

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.