Spectral Graph Theory, Fall 2019

Time: M-W 2:30-3:45. Location: WTS A60

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.

Prerequisites

The main prerequisites for this course are knowledge of linear algebra (say through MATH 222/225 or 230/231), some familiarity with graphs (which you can get from MATH 244, or CPSC 365/366), and comfort with proof-based exposition and problem sets (such as is gained from CPSC 366 or MATH 230/231).

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.

Requirements

There will be 5 or 6 problem sets, and no tests or exams. You may collaborate in small groups on the problem sets. Some of the problems will be hard. The problems sets and related announcements will be distributed via Canvas. Those enrolled in 562 (as opposed to 462) will have extra homework problems.

Topics

Topics I expect to cover in the course include: