Fall 2019 — Spectral Graph Theory

Spectral Graph Theory is a field which studies the properties of a graph in connection to the eigenvalues and eigenvectors of matrices, containing beautiful results which combine linear algebra and graph theory. In this reading group, we will explore these connections and understand how this theory can be applied to design powerful algorithms. Throughout this semester, we will review the essential mathematical background and discuss graphs and their eigenvalues, metric embeddings, the sparsest cut problem, electrical flows, polynomials and Ramanujan Graphs.

Content

First half would look at general problems that can be tackled with spectral methods. Second half will focus on the sparsest cut problem, the current best approximation algorithm for it is.

Resources

We will mostly be covering topics from the following graduate courses on SGT:

1. Spielman, Dan. CS 662: Spectral Graph Theory. Fall 2015. Link.
2. Trevisan, Luca. CS 294: Graph Partitioning, Expanders, and Spectral Methods. Link.

Advice for Presenters

The most important thing about this reading group is for you to get something out of it. Don’t worry about understanding every presentation. As long as you thoroughly understand the material you’re presenting, then you will come out a better theoretician. Here are some general tips:

• Start reading the notes at least a week before the presentation. DON’T try to read all of it at once.
• Don’t be afraid to ask for help whenever you have trouble understanding concepts.
• You don’t have to read all the papers we post thoroughly. If you feel like it’s a bit too much, try reading at least one paper in depth and just get an idea of roughly what the other ones are about. On the other hand, if there are other papers you’d like to incorporate into your presentation, go for it!
• Don’t present every single proof in detail in your presentation, as that will take too long. Make sure you cover all the main ideas and only prove the theorems you think are the most important. Don’t feel bad about omitting proofs of some theorems or just sketching out a rough outline for the proofs. As long as you understand it yourself, it’s okay.

Topics Outline

Introduction

• Linear Algebra Review
• The Laplacian and Adjacency Matrix

Graph Partitioning Algorithms

• Cheeger’s inequality and conductance
• Max cut and k-clustering
• Metric Embedding and sparsest cut

Electrical Flow

• Circuits and spring networks
• Sampling, sparsification and fast linear systems solvers

Expander Graphs and Pseudorandomness

• Constructing expander graphs
• Random walks and pseudorandom number generators

Algebra and Polynomials

• Cayley graphs of abelian groups
• Random matchings and expected characteristic polynomials
• Interlacing polynomials and Ramanujan graphs