1. More applications
1.1. Sorting networks
These are communication networks which are oblivious (do not make any decision based upon content). Input: real numbers. Output: the same, ordered.
Theorem 1 (Ajtai, Komlos, Szemerédi) There is an explicit sorting network of size .
Corollary 2 There is an explicit monotone Boolean formula for Majority
After a randomized existence proof of Valiant.
1.2. Deterministic error reduction
Assume algorithm makes mistakes with probability . Modify it so that probability of error gets smaller.
Trivial solution: repeat algorithm on same input times and take majority. Chernoff’s bound gives exponentially decaying error probability. This requires random bits.
On the set of input strings, put the edges of an expander. Then do steps of random walk on the resulting graph and take majority.
Theorem 3 (Ajtai, Komlos, Szemerédi) Same exponential decay with merely random bit.
1.3. Metric embeddings
Bourgain showed that every -point has a embedding into . This is sharp.
Theorem 4 (Linial, London, Rabinovich) Expanders, when embedded in , incur distorsion at least .
Proof: Convert spectral gap into a Poincaré inequality
A coarse embedding of a metric space to has sandwiched between to functions of
Theorem 5 (Gromov) There exists a finitely presented group whose Cayley graph has not coarse embedding into .
Proof: Contruct in such a way that its Cayley graph contains a sequence of larger and larger expander graphs.
1.4. Non linear spectral gaps
Theorem 6 (Matousek) Expanders satisfy -valued Poincaré inequality
See Mendel’s talk.
2.1. Cayley graphs of finite groups
Which Cayley graphs are expanding ?
Examples by Margulis, Gaber-Galil, Alon-Milman, LPS, Nikolov, Kassabov,…
Mother example is Selberg’s congruence quotients of . It gives rise to a strongly explicit expander : Takes bits to describe a matrix in .
See Gamburd’s course.
2.2. Combinatorial construction: the zig-zag product
Given graphs and , there zig-zag product is a graph whose
- vertices come in clouds modelled on , indexed by ;
- edges correspond to 3 steps walks: one step in cloud 1, one step between clouds, one step in cloud 2.
There is some freedom in the construction.
Theorem 7 (Reingold, Vadhan, Wigderson) If is an -graph and an -graph, is a -graph.
Proof: Expansion implies that entropy of distribution increases under random walk. And conversely. Many choices of entropy work (see Mendel’s talk).
Random walk in amounts to one step of random walk in (increase entropy, strictly if conditional entropy is far from maximum), then one step of random walk in , (increase entropy, strictly if conditional entropy is far from maximum), then one step of random walk in (increase entropy, strictly if conditional entropy is far from maximum). If total entropy is not close to maximum, one of the conditional entropies is too.
2.3. Iterative construction of expanders
Start with a constant size -graph (can be constructed by hand). Let , . Then is a -graph. Indeed, squaring squares the spectral gap.
- Isoperimetric inequalities beating eigenvalue bounds.
- New expanding Cayley graphs for non-simple groups [Meshulam, Wigderson]
2.5. How to escape mazes
Theorem 8 (Aleliunas et al., 1980) On any connected regular graph, random walk will visit every vertex in steps with high probability.
Omer Reingold could derandomize this algorithm. The solution uses zig-zag products. Let be the given graph. Form . After a logarithmic number of steps, is an expander. Try all paths of length . They will cover all vertices of . Construction of from is local, it can be done in a bounded time and space, so describing neighbors in requires space at most .
2.6. Semi-direct products of groups
Let , be groups, let act on by automorphisms. Define multiplication
Example 1 Let and cyclically permuting coordinates. Then semi-direct product is wreath product .
Theorem 9 (Alon, Lubotzky, Wigderson) Semi-direct product of groups yields zig-zag product of Cayley graphs, provided generating set in is a single -orbit.
Corollary 10 Expansion is not a group property, i.e. it depends on generating set.
Use and .
Since Kassabov gave a better example: symmetric group .