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.1. In pure math
Topology (Brooks, Gromov)
Group theory (Babai, Lubotsky-Pak)
Measure theory (Drinfeld and Rusiewicz’ problem)
2. Definition and basic properties
2.1. Several points of view
Combinatorial: No small cuts
Probabilistic: Fast convergence of random walk
Algebraic: spectral gap
Combinatorial: Edge expansion of a set number of edges joing to . Edge expansion is . For random graphs, we expect it to be bounded below by degree.
Probabilistic: We expect the random walk to mix it all in steps.
Algebraic: Use normalized adjacency matrix , second largest eigenvalue.
All three definitions are equivalent. For instance, starting from arbitrary distribution , after steps of random walk, the distribution becomes
This converges exponentially fast to uniform distribution, with speed controlled by .
Lemma 1 (Alon Chung) Let be the number of edges joining subset to . Then
3. Existence and basic parameters
Pinsker: Random -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 of vertices, . Then
Then do union bound over all sets of a given size, and sum over sizes.
Challenge: Construct (weakly, resp. strongly) explicit examples. I mean, give an algorithm which constructs an -vertex expander in polylog time (resp. constructs all tables of neighbors in polylog time).
3.1. How small can be ?
Replacing graph with shows that can be as small as a negative power of degree.
For fixed degree,
Theorem 2 (Alon, Boppana) For degree graphs,
Proof: Trace trick (see Gamburd’s first course).
Probabilistic way to express edge expansion.
Theorem 3 Picking edges at random,
- Every set of size contains an edge.
- Chromatic number has to be large.
- Removing fraction of the edges leaves a connected component of size .
- Every subset of size contains at most vertices with neighbors in .
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 . Then iff a majority of its neighbors are in , and so on. Then for .
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 . Given circuit for a Boolean function with size , construct such that with high probability, and samll size.
Add identity gates, replicate the circuit and insert majority gates… requires 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 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 . We want, for every and every set of input vertices and output vertices, 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 . This does the job.
3.5. Distributed computing
Theorem 7 (Alon, Capalbo) Let be a sufficiently strong expander. Given pairs of vertices, one can efficiently find the set of path connected pairs and find edge-disjoint paths between them, on-line.