Spectral Graph Theory-Summer 2015
Spectral graph theory mostly deals with spectrum of
the
Laplacian of a graph. While graph Laplacians have many similarities
with Laplacians of Riemannian manifolds, the study of them requires
less technical know how. In particular, while mathematical
sophistication will be essential, the only prerequisite for this course
is a good understanding of linear algebra and multivariable calculus.
No prior familiarity with graph theory will be assumed. The advantage
of working with graphs is that many ideas of spectral geometry and
analytic numbers theory can be studied in a very concrete manner. With
the ever increasing role played by large networks and big data in every
day life, ideas developed in spectral graph theory are gaining
importance in many fields now. Note: this is not a graph theory course!
Time permitting, we shall try to cover some (hopefully all!) of the following topics:
Laplacian of a graph and its eigenvalues,
Isospectral but not isometric graphs,
Cheeger inequlaity,
Random walks on graphs, Markov chains, Approach to equilibrium, Ergodicity,
Dirichlet boundary value problems for graphs,
Phase transition in planar Ising model,
Matrix-tree theorem,
Heat kernel techniques,
Counting periodic orbits, Ihara zeta function of a graph, and its Riemann hypothesis.
Marking Policy: 70% assignments, 30% project. Projects will be chosen in consultation with each student, and usually reflect student’s area of specialization or interests. I expect students to prepare a short essay on their project and present it in class in a 50 minutes lecture towards the end of the term. Students should make sure to see me no later than 3 weeks after the start of the class regarding their projects.
Prerequisites:
Linear algebra, mathematical maturity and sophistication.Topics per day:
You can find pdf file of the topics Discussed in each class here.Assignments:
Student Presentations
Disclaimer:
Here are the topics and notes: