Description

A graph is a collection of vertices connected by edges. We can associate matrices to a graph. For example, the adjacency matrix encodes the connections between vertices, the degree matrix encodes the degree of each vertex, and the Laplace matrix can be defined as the difference between the degree matrix and the adjacency matrix.

The focus of this project is to explore what the eigenvalues of these matrices can (or cannot) tell us about the structure of the graph. For example, can the eigenvalues tell us whether the graph is connected?

Group Project

• Recap of spectral results from Linear Algebra.
• Applications of spectral results from Linear Algebra to matrices associated with graphs.
• The Courant-Fischer Theorem.
• The Perron-Frobenius Theorem.
• Edge and Vertex Monotonicity of Eigenvalues.
• Spectral Theory of Bipartite Graphs.
• Vertex Connectivity and the Second Laplace Eigenvalue.

Mode of operation and evidence of learning

Students will demonstrate their understanding of the subject matter by solving relevant problems, exploring and constructing examples, investigating theoretical applications of the material, and clearly communicating it in both written and oral formats.

Individual Project

• The Matrix-Tree Theorem which asserts that the eigenvalues of the Laplace matrix can tell us the number of spanning trees in a graph.
• Spectral bounds for the chromatic number of a graph.
• The Cheeger Inequality which gives us a way of measuring how we can split a graph into two in such a way that its boundary is smallest.
• Nodal Domains on graphs.
• Other eigenvalue problems on graphs (e.g., the Steklov problem).

Mode of operation and evidence of learning

Students will demonstrate their understanding of the subject matter by solving relevant problems, exploring and constructing examples, investigating theoretical applications of the material, and clearly communicating it in both written and oral formats.

Prerequisites and Companion modules

Co-requisites: Analysis & Topology III.

Note that it is not necessary for you to have taken the module Discrete Mathematics I in order to choose this project. If you did take Discrete Mathematics I, then you may already be familiar with some of the terminology surrounding graphs. But, as the focus of this project is on Analysis and Linear Algebra on graphs, I don't feel that you would be at a disadvantage if you didn't take Discrete Mathematics provided that you are willing to brush up on the relevant terminology surrounding graphs at the start of the project.

Note for MMath students about potential links to fourth-year modules: Several of the results that we will explore in this project in the setting of graphs have analogues in the setting of continuous objects (e.g., sets in Euclidean space, surfaces, manifolds). To work in the continuous setting, we would appeal to methods of Functional Analysis that you'll get to explore in your fourth year if you take the module Functional Analysis & Applications IV. If you think you might be interested in that direction, then you might enjoy this project as a first taste.

Some Resources

• K. Naderi, K. Pankrashkin. Introduction to Spectral Graph Theory. Compact Textbooks in Mathematics. Birkhauser Cham. 2026.
• P. Kurasov. Spectral Geometry of Graphs. Operator Theory: Advances and Applications. Birkhauser Berlin, Heidelberg. 2023.
• O. Post. Spectral Analysis on Graph-like Spaces. Lecture Notes in Mathematics. Springer Berlin, Heidelberg. 2012.
• Wikipedia page on Spectral graph theory.