Spectral Graph Theory, Fall 2018

Time: M-W 2:30-3:45. In WTS A60. (Watson Center is 60 Sachem St, NOT AKW)

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

CPSC 662/AMTH 561, is a graduate course on Spectral Graph Theory and related topics. It is taught in the style of a math class, and will cover a bunch of theorems, a few algorithms, and many open problems. I have chosen to only present material that I consider beautiful. My other goals are to present material that is useful and to introduce fundamental concepts. 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.

The obvious prerequisites for this course are knowledge of linear algebra and exposure to graph theory. At Yale, this probably means Math 244 or CPSC 365, and at least one of Math 230/231, 300 or 301. The less obvious requirements are "mathematical maturity" and "mathematical literacy". I will sometimes make use of concepts that every graduate student in Mathematics should know. This means I will assume students are acquainted with finite fields, groups, and elementary aspects of real analysis, complex analysis and topology. I assume that students who are not familiar with these can look them up.


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.

I will occasionally include material in my lecture notes that I will not have time to cover in class. You are responsible for that material.


I will not assign a book for this course. Rather, I will produce notes for all the lectures.

Should you take this course?

You can get a good feel for what this course will be like by looking at the lecture notes from previous years. Here are the notes from 2015, 2012, 2009, and 2004. You should take this course if you For a sales pitch for the type of material I cover in this course see the notes from my first lecture in 2009. This course is suitable for some advanced undergraduates. But, I warn them that it will move at a fast pace (faster than CPSC 366) and will not be nearly as friendly as a typical undergrad course. I don't yet know if we will have a TA.


Topics I expect to cover in the course include: