## 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. Then

$\displaystyle \begin{array}{rcl} \mathop{\mathbb P}(|\partial S|

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