Expanders

Expander graphs and Applications. Semester B 2017.  Tuesday 4-7. Room Shenkar 204. Tel Aviv University

G=(V=F_p-{p-1,0,1}, E=(x~x-1,x~x+1,x~1/x)) for p=757. |lambda|~2.907. Created with sage.

F_p graph with edges (p-1,p+1,1/p) for p=757

Requirements: Basic notions of probability theory. Linear algebra. Some finite field arithmetic. Fourier series on R^2/Z^2 for Chapter 2. 

Topics 6 and 7 will use spectral theory on Hilbert spaces (we will recall what we need). Chapter 6-8 will require stamina for calculations of 3 times 3 matrices. 

Lectures:

Topics
14.03.2017 Roughly following the HWL-survey :
Definition 2.1, Definition 2.2, Section 2.2 Examples,
Section 2.3 Properties of lambda and Theorem 2.4
Last bullet point of Section 2.4
Lemma 4.7, formula (1) of 4.3.1
Rayleigh Quotient
22.03.2017 Definition of Schreier Graph, (e.g. HLW 11.1.2)
SL_2(Z) and ASL_2(Z)
Margulis' Theorem
Proof of Gabber Galil Theorem (up to Claim 3 in their paper )
28.03.2017 Finished proof of of Gabber Galil Theorem.
Discussion on Optimality on the infinite graph on primitive points. (from the Appendix of their paper)
Section 3.3.1 HLW: Efficient error reduction in probabilistic algorithms.
03.04.2017 Miller-Rabin primality test (following these course notes of G. Valiant)
Theorem 3.2 and 3.6 of the HLW-survey on rapid mixing of random walks
25.04.2017 Zig Zag product ( Paper of RVW or HLW Section 9)
09.05.2017 Property (T) for ASL_2(R) and SL_3(R) (e.g. Morris Witte book Chapter 13 )
16.05.2017 Quantitative Property (T):
Effective Decay of Matrix coefficients for ASL_2(R) (Two different proofs of Einsiedler and Howe-Tan ).
Explicit uniform spectral gap parameters for ASL_2(Z) (Result of Burger , we give the proof of Shalom, Chapter 2 )
23.05.2017 Selberg's Theorem on Property (tau) for congruence quotients of SL_2(Z)
Step 1: Kloosterman Sums and Equidistribution on T^2
06.06.2017 Step 2: Equidistribution of closed horocycles
13.06.2017 Step 3: Effectiving Mixing and uniform spectral gap
27.06.2017 Euclidean Embeddings of finite metric spaces. Chapter 15 in Lectures on Discrete Geometry by Jiří Matoušek


Exercise Sheet (will be updated during the semester. Deadline: September 1. You should try at least 1/3 of the exercises): exercises (final)

Syllabus:

  1. A first encounter with graphs (1 lecture)
    • Spectral definition
    • Mixing Lemma
    • Cheeger constant
    • Existence of Expanders & 2 examples
  2. Construction 1: The first explicit construction: Margulis-Gabber-Galil Expanders (2 lectures)
    • Margulis Construction using Kazhdan's Property (T)
    • Quantitative proof by Gabber-Galil
  3. Application 1: Random Walks and Probability Amplification (1 lecture)
    • In context: Miller-Rabin primality test
  4. Construction 2: Zig-Zag product (Reingold-Vadhan-Wigderson) (1 lecture)
  5. Kazhdan's Property (T) of SL_3(R)  (1 lecture)
    • Mautner phenomenon
  6. "Quantitative Kazhdan's Property (T)": Kazhdan constants for (ASL_2(Z),Z^2) (2 lectures)
      • Explicit generator set (Burger) 
      • Any generator set using bounded generation (Shalom) 
  7. Selberg's Theorem on congruence quotients (3 lectures)
  8. Application 3: Euclidean Embedding of finite metric spaces and Bourgain's Theorem (1 lecture)
  9. Construction 3: Margulis construction
    • Property (tau) of SL2(Z)

References: