Instructor: | David P. Williamson |
---|---|

Office: | Rhodes 236 |

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

Office phone: | 255-4883 |

Email: | My three initials AT cs.cornell.edu |

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.

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

- 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.