Spectral Graph Theory

Fall 2016

Instructor Information

Instructor: Office: Office hours: Office phone: Email:

David P. Williamson

Rhodes 236

M 11-12, Wed 1:30-2:30, and by appointment

255-4883

My three initials AT cs.cornell.edu

Overview

The course meets Tuesdays and Thursdays in Rhodes 571 from 10:10-11:25AM. It will also be broadcast to Cornell NYC Tech, Ursa room.

This course will consider connections between the eigenvalues and eigenvectors of graphs and classical questions in graph theory such as cliques, colorings, cuts, flows, paths, and walks. Both older structural results and recent algorithmic results will be presented. Topics to be covered include the matrix-tree theorem, Cheeger's inequality, Trevisan's max cut algorithm, bounds on random walks, Laplacian solvers, electrical flow and its applications to max flow, spectral sparsifiers, and the Colin de Verdiere invariant. Additional topics may include the Arora-Rao-Vazirani algorithm for sparsest cut, sampling spanning trees, and recent higher-order Cheeger inequalities.

Handouts

Handout 1: Course Information

Scribing materials

LaTeX macros for scribing

Lectures

Aug 23 Aug 25 Aug 30 Sept 1 Sept 6 Sept 8 Sept 13 Sept 15 Sept 20 Sept 22 Sept 27 Sept 29 Oct 4 Oct 6 Oct 11 Oct 13 Oct 18 Oct 20 Oct 25 Oct 27 Nov 1 Nov 3 Nov 8 Nov 10 Nov 15 Nov 17 Nov 22 Nov 29 Dec 1

Introduction. Warmup: bounds on d-regular Moore graphs of diameter two. (Hoffman-Singleton 1960)

Eigenvalue basics. (Trevisan, Ch. 1; Lau, Lecture 1)

Eigenvalue identities. The Perron-Frobenius theorem. Bipartite graphs. (Lau, Lecture 1; Spielman, Lecture 3)

Eigenvalue interlacing. Bounds on clique and chromatic numbers. (Some notes of Embree; Spielman, Lecture 3)

Graph Laplacians. Algebraic connectivity. Some easy bounds on bisection and max cut. (Lau, Lecture 2; Cvetković et al, Section 7.4; Mohar and Poljak, Sections 2.1 and 2.5)

Graph Laplacians and the matrix-tree theorem. (Cvetković et al, Sections 7.1, 7.2; Godsil and Royle, Section 13.2)

Normalized Laplacians. Cheeger's inequality. (Lau 2012, Week 2)

Cheeger's inequality cont. Trevisan's bound on the largest eigenvalue. (Lau 2012, Week 2; Lau, Lecture 4)

Trevisan's spectral approximation algorithm for MAX CUT. (Lau 2012, Week 2; Lau, Lecture 4)

Computing eigenvectors and eigenvalues. (Trevisan, Chapter 4; Vishnoi, Chapter 8)

Random walks I: stationary probabilities, convergence, mixing time. (Lau, Lecture 7)

Electrical flows. Effective resistance, energy. (Lau, Lecture 12)

More about effective resistance. Random walks II: hitting time, cover time. (Bollobás II.1; Lau, Lecture 12; Motwani, Raghavan 6.3-6.5)

Low-stretch spanning trees. (Harvey, Cargèse Lecture 1)

Fall break.

Iterative methods and preconditioning. (Spielman, Lecture 12; Spielman and Woo 2009)

A simple combinatorial algorithm for solving Laplacian systems. (Kelner, Orecchia, Sidford, and Zhu 2013; Lau, Lecture 13)

The multiplicative weights update algorithm. (Arora, Hazan, and Kale 2012)

Max flow in undirected graphs. (Christiano, Kelner, Mądry, Spielman, and Teng 2010; Lau, Lecture 15)

Matrix Chernoff bounds. (Harvey, Cargèse Lecture 2)

Spectral sparsifiers. (Harvey, Cargèse Lecture 3; Lau, Lecture 17; Spielman and Srivastava 2011)

Matrix multiplicative weights update and deterministic sparsifiers. (Arora and Kale 2016; Kale's 2007 thesis; de Carli Silva, Harvey, and Sato 2015)

Linear-sized spectral sparsifiers. (Batson, Spielman, and Srivastava 2014; Spielman, Lecture 18)

Generalized Laplacians, planarity, and the Colin de Verdière invariant. (Godsil and Royle, Sections 1.8, 13.9-13.11; Van der Holst 1995)

No class.

Kyng-Sachdeva algorithm overview. (Kyng and Sachdeva 2016)

Arora-Rao-Vazirani sparsest cut algorithm: Leighton-Rao algorithm. Negative-type metrics. Connection to Cheeger inequalities. (Leighton and Rao 1999; Sudan and W unpublished note)

Arora-Rao-Vazirani sparsest cut algorithm: The algorithm. Reduction to the Structure Theorem. (Rothvoss 2016 lecture notes; W and Shmoys, Section 15.4; Barak and Steurer 2016 lecture notes)

Arora-Rao-Vazirani sparsest cut algorithm: Proof of the Structure Theorem. (Barak and Steurer 2016 lecture notes)

Structure Theorem Lecture Remix

Problem Sets

• Problem Set 1, due September 20.
• Problem Set 2, due October 6.
• Problem Set 3, due November 3.
• Problem Set 4, due November 22.

Other course notes and resources

• Lap Chi Lau, University of Waterloo, Fall 2015.
• Dan Spielman, Yale University, Fall 2015.
• Luca Trevisan, UC Berkeley
  • Stanford course, Winter 2011.
  • Course notes.
• Nisheeth Vishnoi, EPFL, Lx = b.
• Chris Godsil and Gordon Royle, Algebraic Graph Theory.
• Dragoš Cvetković, Peter Rowlinson, Slobodan Simić, An Introduction to the Theory of Graph Spectra.
• Bojan Mohar and Svatopluk Poljak, Eigenvalues in Combinatorial Optimization.
• Béla Bollobás, Modern Graph Theory.
• Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms.