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

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.

- like pretty math,
- anticipate needing to prove theorems later in your life, or
- want to understand eigenvalues and eigenvectors and what they mean.

- An introduction to the "animals in the Zoo": the spectra of some fundamental graphs: paths, trees, rings, grids, hypercubes, cayley graphs, strongly regular graphs and random graphs. Also, fundamental polynomials like those of Chebyshev, Hermite, and Laguerre.
- Graph coloring.
- Cheeger's inequality: probably at least two different proofs of it and some generalizations.
- Graph partitioning in random models (Stochastic Block Models).
- Analysis of random walks on graphs, and Poincare inequalities.
- Connections to Spring and Electrical networks.
- Schur complements, effective resistance and some of their applications.
- Tutte's theorem on drawing planar graphs using Spring networks.
- Bounds on the Fiedler value of planar graphs.
- Expander graphs and some of their applications.
- Ramanujan graphs and a proof of their existence.
- Graph Sparsification and its connection to the Kadison-Singer Problem.
- Testing graph isomorphism.
- Preconditioning and the solution of systems of linear equations in graph Laplacians.
- The matching polynomial of a graph.