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.

Advertisements

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 http://www.math.ens.fr/metric2011/
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:

WordPress.com Logo

You are commenting using your WordPress.com 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