Notes of Avi Wigderson’s lecture nr 3

1. Consequences of the zig-zag product

  • {SL=L}, 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 {G} is {k}-step colvable and {Cay(G,S)} is expanding, then

\displaystyle  \begin{array}{rcl}  |S|\geq \Omega(\log\log\cdots\log|G|), \end{array}

with {k} logs.

This is essentially sharp, as we show with Meshulam. Start with {G_1 ={\mathbb Z}_2} and iterate semi-direct product {G\mapsto G'=G\times F_q^G}.

Conjecture: If {Cay(G,S)} is expanding, then {G} has at most {e^d} irreducible representations of dimension {d}.

[De la Harpe, Robertson, Valette]: True if {e^d} is replaced with {e^{d^2}}.

[Meshulam, Wigderson]: True with {e^d} for monomial groups.

2.2. Iterated wreath products

Iterate {G_{k+1}=G_k \wr \mathfrak{A}_k}. Then {G_k} is the group of even automorphisms of a rooted depths {k} tree.

Theorem 2 (Rozenman, Shalev, Wigderson) {Cay(G_k ,S_k )} is expanding with explicit bounded number of generators.

3. Beating eigenvalue bounds

Task: Given {a}, construct a low degree graph such that every two sets of size {N/a} are connected by an edge.

Ramanujan graphs achieve {d=\Omega(a^2)}.

Random graphs achieve {d=O(a\log a)}.

Zig-zag graphs achieve {d=O(a(\log a)^{O(1)})}.

3.1. Applications

Sorting and selection in rounds, superconcentrators.

3.2. Lossless expanders

Task: Construct a {d}-regular gra ph in which every set {S} of size {|S|\ll n/d} has vertex expansion {\geq c}.

Obviously {c\leq d}.

Ramanujan graphs achieve {c\geq d/2}. [Kahale]

Note that {d/2} is a key threshold for applications.

Random graphs achieve {c\geq (1-\epsilon)d}. These are called lossless expaders.

Zig-zag graphs achieve {c\geq (1-\epsilon)d}. [Capalbo, Reingold, vadhan, Wigderson].

Many applications, here is one.

4. Error correcting codes

Recall that a code {C:\{ 0,1 \}^k\rightarrow\{ 0,1 \}^n} 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 {G} is lossless, then encoding time is linear.

4.2. Decoding

theorem We can construct graphs with {k=n/2}, right degree {=10} and suchthat any set {B} of size {|B|\leq n/200} has vertex expansion {\geq 9}.

Sipser, Spielman:While {PW\not=0}, flip all {w_i} with {i\in FLIP=\{i\,;\, \Gamma(i)} has more {1}‘s than {0}‘s{\}}

They show that the number of corrupted positions falls by a factor of {2} 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 {K}, 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 {K}. The limiting distribution is uniform in {K}. 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 {2}-dimensional grid.

Use Glauber dynamics, i.e. MCMC sampling the Gibbs distribution. For this, construct a graph {H} 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 {S} of a finite (matrix) group, sample (approximately) elements of the group {G} generated by {S} from the uniform distribution.

[Babai, Szemerédi] introduced the product replacement algorithm: change {S} by changing generator into inverse or multiplying two generators.

Theorem 3 (Babai, Szemerédi) Every element is reached in time {\leq O((\log n)^2)}.

Theorem 4 (Cooperman, Dixon, Green) The procedure produces near random element in time {\leq O((\log n)^2)}.

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 {T_1 ,\ldots, T_k :F^n \rightarrow F^n} is a dimension expander if for every subspace {V\subset F^n} of dimension {\leq n/2}, there exists {i} such that

\displaystyle  \begin{array}{rcl}  \mathrm{dim}(T_i \cap V)<(1-\epsilon)\mathrm{dim (V)}. \end{array}

A bounded number of random linear maps does the job. [Lubotzky] gave an explicit construction in characteristic {0}. [Dvir, Shpilka] could construct {\log n}-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.


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
This entry was posted in Course, Workshop lecture and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s