Description
Graphs are fundamental mathematical tools to describe various discrete configurations and settings appearing both theoretically and in practice. These objects lie at the interface between combinatorics, linear algebra, geometry, and analysis. In this project, we will learn how to associate to a combinatorial graph with vertices and edges a symmetric matrix, the adjacency matrix, which identifies the edges between vertices. Since this matrix is symmetric, all its eigenvalues are real and we will discuss various information which can be extracted from these eigenvalues. There are many other matrices that can be associated to a graph, and we will discuss many aspects of them. The topic runs under the title "Algebraic Graph Theory" or "Spectral Graph Theory''.
What is a graph?
In this project we consider only finite graphs. Such a graph \(G\) is a pair \(V,E\) of two finite sets \(V\) and \(E\), the vertex set and the edge set, respectively, where the vertices can be viewed as points and and edges can be viewed geometrically as arcs connecting a pair of (not necessarily distinct) vertices. However, we completely forget this geometric picture and are only interested in the information about the end-points of edges. An enumeration of the vertices leads to a specific symmetric matrix, the adjacency matrix \(A=A_G\) with non-negative integer-valued entries describing the number of edges between any pair of vertices.What is the spectrum of a graph?
The adjacency matrix \(A_G\) is symmetric and its eigenvalues are therefore all real numbers. They are called the (adjacency) spectrum of a graph \(G\). These eigenvalues carry a surprising amount of information about the underlying graph.The goal of this project is to introduce and explore the spectra of various matrices associated to graphs and to investigate the information provided by these spectra.
Group project
The group project will revolve around learning basic concepts and results in this topic. By the end of the group project we would have learned- Various families of graphs and their properties.
- Graph constructions like Cartesian products and lifts.
- The definition of various matrices associated to a graph.
- Geometric and topological information contained in graph matrices.
- How discrete groups with certain choices of generators can be geometrically represented by graphs (Cayley graphs).
Mode of Operation and Evidence of Learning for the group project
The project will revolve around learning through reading with focus on the underlying theory, mathematical rigour, and the development of deep conceptual understanding. Students will demonstrate their understanding by investigating relevant problems, exploring examples and theoretical applications of the material, and clearly communicating it in both written and oral formats.Individual project
The individual project will build on the knowledge we have gained in the group project and will explore additional advanced topics. A few examples of topics you will be able to investigate are:- Ramanujan and expander graphs.
- Properties of distance-regular graphs.
- Random walks on graphs.
- Electric networks.
- Graphs and Coding Theory.
- Graph Laplacians and semigroups.
Mode of Operation and Evidence of Learning for the individual project
The project will revolve around learning through reading with focus on the underlying theory, mathematical rigour, and the development of deep conceptual understanding. Students will demonstrate their understanding by investigating relevant problems, exploring examples and theoretical applications of the material, and clearly communicating it in both written and oral formats.Prerequisites and Co-requisites
Prerequisites : Analysis I, Linear Algebra I, Algebra II.
Additional information
If you would like more information about this project, discuss its scope and/or its prerequisites, don't hesitate to contact me at norbert.peyerimhoff@durham.ac.uk
Resources
- Norman Biggs: Algebraic Graph Theory.
- Andries E. Brouwer & Willem H. Harmers: Spectra of Graphs.
- Fan R. K. Chung: Spectral Graph Theory.
- Mike Krebs & Anthony Shaheen: Expander Families and Cayley Graphs, A Beginner's Guide.
- A. E. Brouwer, A. M. Cohen & A. Neumaier: Distance-Regular graphs.
- Ron M. Roth: Introduction to Coding Theory.
- Peter G. Doyle & J. Laurie Snell: Random Walks and Electric Networks.
- Mattias Keller, Daniel Lenz & Radosław K. Wojciechowski: Graphs and Discrete Dirichlet Spaces.