This course provides a comprehensive introduction to spectral and algebraic graph theory, focusing on the interplay between graph structure and eigenvalues of associated matrices. The course covers both theoretical foundations and practical applications in computer science and engineering.

Course Description

Graphs are fundamental mathematical structures used to model pairwise relations between objects. In spectral graph theory, we study graphs through the eigenvalues and eigenvectors of matrices associated with the graph, such as the adjacency matrix or Laplacian matrix. In algebraic graph theory, we use algebraic techniques to study graph properties.

This course explores:

1. Basic concepts in graph theory
2. Matrix representations of graphs
3. Spectral properties of graph matrices
4. Graph partitioning and clustering
5. Random walks on graphs
6. Applications in machine learning and data analysis
7. Advanced topics in algebraic graph theory

Prerequisites

• Linear Algebra
• Basic Graph Theory
• Mathematical Maturity

Textbooks

• Fan R. K. Chung, “Spectral Graph Theory”, American Mathematical Society, 1997.
• Dragos M. Cvetkovic, Peter Rowlinson, and Slobodan K. Simic, “An Introduction to the Theory of Graph Spectra”, Cambridge University Press, 2009.

Assessment

• Homework assignments (40%)
• Midterm exam (25%)
• Final project (35%)