Prerequisites: (CS2020A Discrete Mathematics OR CS5021/13 Topics in Discrete Mathematics OR CS5010 Graph Theory and Combinatorics) AND (MA1011 Linear Algebra and Series OR MA5001 Linear Algebra)
Course Overview
Spectral Graph Theory is the study of curious connections between eigenvalues of matrices associated with a graph and some combinatorial properties of the graph. Some of these connections have been used to solve algorithmic problems on very large networks.
Course Content
Introduction. Matrices associated with a graph. Review of spectral theory of real symmetric matrices. Spectra of standard graphs. Initial examples of connections between spectrum and structure of a graph. The Laplacian matrix and graph drawing. [6 lectures]
Important tools from spectral theory. Eigenvalues and optimization (Courant-Fischer Theorem). Cauchy’s Interlacing Theorem and Perron-Frobenius Theorem for Symmetric Matrices. Adjacency matrices and eigenvalue interlacing. [6 lectures]
Physical metaphors Random walks on graphs. Springs and resistor networks. [6 lectures]
Spectra and graph structure Independent sets and coloring. Graph partitioning. Cheeger’s Inequality. Graph clustering. Nodal Domains [12 lectures]
Expander Graphs. Properties of expander graphs. Simple constructions. [6 lectures]
Selected Topics. One of the following topics: Spectra of random graphs, Random spanning trees, Sparsifiers, Spectra of planar graphs or Cayley graphs. [6 lectures]
Learning Outcomes
Students who successfully complete the course will be able to
- State and prove many connections between spectral and combinatorial properties of graphs.
- Apply the above connections to give bounds on some graph parameters
- Apply the above connections to design graphs with certain desired properties
Text Books
- Spectral and Algebraic Graph Theory by Daniel A. Spielman. Available online from the author’s homepage.
References
-
Algebraic Graph Theory by Norman Biggs. Cambridge University Press. ISBN: 978-0521458979
-
Spectral Graph Theory by Fan Chung. American Mathematical Society, ISBN: 978-0821803158
-
Algebraic Graph Theory by Chris Godsil and Gordon Royle. Springer. ISBN: 978-1461301639
-
Lecture Notes on Expansion, Sparsest Cut, and Spectral Graph Theory by Luca Trevisan. Available online.
Past Offerings
Course Metadata
| Item | Details |
|---|---|
| Course Title | Spectral Graph Theory |
| Course Code | CS5659 |
| Course Credits | 3-0-0-3 |
| Course Category | PME |
| Proposing Faculty | Deepak Rajendraprasad |
| Approved on | Senate of IIT Palakkad |
| Course prerequisites | First Courses in Graph Theory/Discrete Math and Linear Algebra |
| Course status | new |