Schedule of Lectures

• 8/25:
  
  • Lecture: Recurrence vs. transience of random walks. “Brute-force” proof of recurrence for random walks in the 1D and 2D grid.
  • Reading: None.
  • Scribe notes by Brad Gulko, in preparation.
• 8/30 and 9/1: Class canceled.
• 9/6:
  
  • Lecture: “Brute-force” proof of transience for random walk in the 3D grid. Proofs of recurrence vs. transience for grids via spectral analysis of torus graphs.
  • Reading: None.
  • Scribe notes by Bruno Abrahao.
• 9/8: Class canceled due to flooding.
• 9/13:
  
  • Lecture: Electrical networks and harmonic functions on graphs.
  • Reading: Doyle and Snell, Chapter 1.
  • Scribe notes by Chaoxu Tong.
• 9/15:
  
  • Lecture: Rayleigh monotonicity. Electrical flows in infinite graphs and their relation to recurrence vs. transience. Proof of recurrence for 2D grid using electrical networks.
  • Reading: Doyle and Snell, Chapter 2.
  • Scribe notes by Anna Blasiak, in preparation.
• 9/20:
  
  • Lecture: Proof of transience for 3D grid using electrical networks. Effective resistance, commute time, and cover time. Kirchhoff's matrix-tree theorem.
  • Reading: Doyle and Snell, Chapter 2.
  • Scribe notes by Pramook Khungurn, in preparation.
• 9/22:
  
  • Lecture: The matrix-tree theorem and effective resistances. Wilson's algorithm for sampling spanning trees.
  • Reading: Lyons and Peres, Chapter 4.1.
• 9/27:
  
  • Lecture: Laplacian eigenvalues, Courant-Fischer, and Cheeger's Inequality.
  • Reading: Luca Trevisan's lecture notes on eigenvalues and eigenvectors and on the easy direction of Cheeger's Inequality. For a discussion of the Courant-Fischer Theorem, see these lecture notes by Dan Spielman.
• 9/29:
  • Lecture: Finish proof of Cheeger's Inequality.
  • Reading: Luca Trevisan's notes on the hard direction of Cheeger's Inequality.
• 10/4:
  • Lecture: Eigenvalues of planar graphs, and the Lipton-Tarjan Planar Separator Theorem.
  • Reading: D. Spielman and S.-H. Teng, Spectral partitioning works: Planar graphs and finite element meshes (Linear Algebra and its Applications 421 (2-3), 2007, original version appeared in FOCS 1996).