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.
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.
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.
Resources
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
- like pretty math,
- anticipate needing to prove theorems later in your life, or
- want to understand eigenvalues and eigenvectors and what they mean.
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
Topics I expect to cover in the course include:
- 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.