LEAPS-MPS: Algebraic Methods in Spectral Graph Theory

A graph is a collection of objects (vertices) and connections between the objects (edges). Models of network systems, such as communities of people and the internet, use graphs. As these graphs grow large, it becomes increasingly difficult to understand and detect structural information.

One way to gain an understanding of large graphs is to use linear algebra tools by associating graphs with matrices in some fashion. Understanding and detecting structures in large matrices seems to have the same challenges as understanding large graphs, but this can be partially overcome by considering the spectrum. The spectrum (multi-set of eigenvalues) of a matrix for a graph gives a snapshot of the graph structure independent of labeling.

This project has two main goals: (1) To determine how the graph structural properties relate to the spectrum of its associated matrix. (2) To establish Wild-Math, an enriching summer research and outreach experience for Linfield University and McMinnville High School students.

This project builds on previous work on finding patterns of graphs (or pairs of graphs) with particular spectral properties and developing and applying linear algebra tools to connect the graph structure with the spectral structure. In particular, this project will focus on finding and developing constructions of cospectral graphs and constructions of graphs with degenerate eigenspaces.

The research component of Wild-Math will consist of a cohort of undergraduate students developing patterns of graph behavior and writing linear algebra proofs. The participants will engage in readings and discussions about issues and solutions for broadening participation in mathematics. The participants, the PI, and collaborators from McMinnville High School will mentor high school students in developing a math-intensive project that they will present at appropriate venues.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.