Notes of Avi Wigderson’s lecture nr 1

Expander graphs, applications and combinatorial construction

I will survey expanders, from a slightly different point of view from Gamburd’s. Most of what I will cover is contained in Howry, Linial and Wigderson’s survey.

1. Applications

1.1. In pure math

Topology (Brooks, Gromov)

Group theory (Babai, Lubotsky-Pak)

Measure theory (Drinfeld and Rusiewicz’ problem)

Number theory

Graph theory

2. Definition and basic properties

2.1. Several points of view

Combinatorial: No small cuts

Probabilistic: Fast convergence of random walk

Algebraic: spectral gap

2.2. Definition

Combinatorial: Edge expansion of a set {|\partial S|=} number of edges joing {S} to {S^c}. Edge expansion is {\frac{|\partial S|}{|S|}}. For random graphs, we expect it to be bounded below by degree.

Probabilistic: We expect the random walk to mix it all in {\log n} steps.

Algebraic: Use normalized adjacency matrix {\frac{1}{d}A}, {\lambda=} second largest eigenvalue.

All three definitions are equivalent. For instance, starting from arbitrary distribution {p}, after {t} steps of random walk, the distribution becomes

\displaystyle  \begin{array}{rcl}  p^t =(A^{\top})^t p. \end{array}

This converges exponentially fast to uniform distribution, with speed controlled by {\lambda}.

Lemma 1 (Alon Chung) Let {E(S,T)} be the number of edges joining subset {S} to {T}. Then

\displaystyle  \begin{array}{rcl}  |E(S,T)-\frac{d}{n}|S||T||\leq dn\lambda. \end{array}

3. Existence and basic parameters

Pinsker: Random {3}-regular graphs are expanders.

We will not define precisely the model. Note that combinatorial expansion is very robust, so definition resistant.

Proof: Fix a set {S} of vertices, {|S|=s<n/2}. Then

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(|\partial S|<s^{...}|S|)<s^{...}. \end{array}

Then do union bound over all sets of a given size, and sum over sizes. \Box

Challenge: Construct (weakly, resp. strongly) explicit examples. I mean, give an algorithm which constructs an {n}-vertex expander in polylog time (resp. constructs all tables of neighbors in polylog time).

3.1. How small can {\lambda} be ?

Replacing graph {G} with {G^d} shows that {\lambda} can be as small as a negative power of degree.

For fixed degree,

Theorem 2 (Alon, Boppana) For degree {d} graphs,

\displaystyle  \begin{array}{rcl}  \lambda >\frac{2\sqrt{d-1}}{d}. \end{array}

Proof: Trace trick (see Gamburd’s first course). \Box

3.2. Consequences

Probabilistic way to express edge expansion.

Theorem 3 Picking edges {uv} at random,

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(u\in S \textrm{ and }v\in T -\mu(S)\mu(T)|<\delta. \end{array}

Corollary 4

  1. Every set of size {\geq \delta n} contains an edge.
  2. Chromatic number has to be large.
  3. Removing fraction {\gamma<\delta} of the edges leaves a connected component of size {>(1-O(\gamma))n}.
  4. Every subset of size {s<n/8} contains at most {s/2} vertices with {>d/3} neighbors in {S}.

We give a consequence of the last item in previous corollary. An infection process on an expanders dies off very fast.

Infection process 1. Infection starts with a subset {S_0}. Then {v\in S_1} iff a majority of its neighbors are in {S_0}, and so on. Then {S_t =\emptyset} for {t>\log n}.

Infection process 2. Infection starts with a collection of subsets

3.3. Fault-tolerant computation

Started with von Neumann. This was Pinsker’s motivation. Reliable circuits from unreliable components. Every gate fails with probability {p<1/10}. Given circuit {C} for a Boolean function {f} with size {s}, construct {C'} such that {C'(x)=f(x)} with high probability, and samll size.

Add identity gates, replicate the circuit and insert majority gates… requires {\leq O(\log(s))} replicates if circuit is an expander. Indeed, analyze in terms of infection.

Nowadays, components are reliable. But it will take a long time before quantum gates get reliable.

3.4. Bipartite expanders

Duplicate vertex set and put edges vertically. This gives a loss of {3/4} on edge expansion. Triplicate and joint every Then every set on the top has a perfect matching on the bottom.

This is used to build concentrators [Bassaligo, Pinsker]

Definition 5 (Valiant) A superconcentrator is a graph with an input set and an output set, each of size {n}. We want, for every {k} and every set of {k} input vertices and {k} output vertices, {k} disjoint paths joining them pairwise.

Theorem 6 (Valiant) The minimal size on a superconcentrator is a lower bound on the size of a linear circuit computing a matrix with all minors nonsingular.

Unfortunately, there exists linear size superconcentrators (Valiant, Pippenger). Indeed, perfect match top to bottom. Add a superconcentrator of size {2n/3}. This does the job.

3.5. Distributed computing

Theorem 7 (Alon, Capalbo) Let {G} be a sufficiently strong expander. Given {k<\frac{n}{\log n}} pairs of vertices, one can efficiently find the set of path connected pairs and find edge-disjoint paths between them, on-line.


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