Leaps-MPS: algebraic methods in spectral graph theory

This National Science Foundation (NSF) Project Grant under the Mathematical and Physical Sciences (CFDA 47.049) program provides $247,348 in funding to Linfield University in McMinnville, Oregon. The grant supports two main objectives: 1) research to determine how graph structural properties relate to the spectrum of associated matrices, and 2) establishing the WILD-MATH program, which provides a summer research and outreach experience for Linfield University and McMinnville High School students. The research component focuses on developing patterns of graph behavior and applying linear algebra tools to connect graph structure with spectral structure, including investigating cospectral graphs and graphs with degenerate eigenspaces. The WILD-MATH program will engage undergraduate and high school students in mathematics-intensive projects and provide mentorship, with participants presenting their work at appropriate venues. This award reflects NSF's priorities of advancing scientific knowledge and broadening participation in STEM fields.

Abstract

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.- subawards are not planned for this award.