*You can find the schedule of lectures and assignments, here.*

The book for the course is on this webpage.

CPSC 462/562 is the latest incarnation of my course course on Spectral Graph Theory. Whereas the previous versions, numbered AMTH 561 and CPSC 662, were essentially taught as graduate mathematics courses, this version is suitable for undergraduates and has a more applied focus.

**Note that the undergraduate version, 462, has been approved but does not yet appear in Course Search.**

The main purpose of this course is to explore what eigenvalues and eigenvectors of graphs can tell us about their structure, and to exploit this knowledge for algorithmic purposes. It will also include some related content that is not strictly linear algebraic, and some that does not have much to do with graphs, but which I include because it is worth knowing.

You could think of this as a course in "Advanced Linear Algebra with examples from Graph Theory." Most lectures will cover some essential element of Linear Algebra or Spectral Theory. You could also think of this as a course in "how to talk with Dan", because I find that almost every research question I address somehow relates back to material covered in this course.

Readings for the course will come from drafts of a book that I am writing, and which I will post on this page. The sections of the book are drawn from my old lecture notes. I hope that it will provide a convenient reference for both the course and for lots of exciting material that we will not have time to cover.

To help you decide if this course is right for you, you can look at the lectures notes from the previous versions, taught in 2018, 2015, 2012, or 2009, 2004. This version of the course will assume less familiarity with a mathematics curriculum. But, it will still move at a very fast pace. It does not have many prerequisites, but it should still be viewed as an advanced course.

- An introduction to the "animals in the Zoo": the spectra of some fundamental graphs: paths, trees, rings, grids, hypercubes, and random graphs.
- Graph drawing.
- Graph coloring.
- Graph partitioning and Cheeger's inequality.
- Graph partitioning in random models (Stochastic Block Models).
- Local graph clustering.
- Analysis of random walks on graphs, and Poincare inequalities.
- Connections to Spring and Electrical networks.
- Schur complements, effective resistance and some of their applications.
- Expander graphs, some of their applications, and connections to error-correcting codes.
- Sparsification.
- Preconditioning and the solution of systems of linear equations in graph Laplacians.