LEAPS-MPS: Bridging Combinatorics and Eigenvalue Multiplicities: Advances in Spectral Graph Theory

Rochester Institute Of Tech, Rochester NY

Investigators

Abstract

Spectral graph theory is the study of networks from a mathematical perspective inspired by sound and vibration. Just as the shape of a musical instrument influences how it resonates and produces tones, the structure of a network determines the eigenvalues and eigenvectors of associated matrices. These spectral properties reveal hidden characteristics of the network, such as clustering, connectivity, or sparsity, which are often not immediately apparent from the graph’s visual representation. By analyzing these properties, spectral graph theory provides a powerful framework for understanding and analyzing complex systems across many domains. Applications range from social networks and transportation grids to biological systems and machine learning models, where uncovering deep structural insights enables researchers to draw general conclusions about entire classes of matrices that share a network’s structural pattern, rather than analyzing individual cases. This project investigates the fundamental relationships between the structural, combinatorial, and spectral properties of matrices associated with graphs, with particular emphasis on the inverse eigenvalue problem for graphs (IEP-G). The IEP-G aims to characterize all possible spectra of real symmetric matrices whose zero–nonzero patterns correspond to the edges of a given graph. Understanding these spectra is critical for linking a graph’s topology to its spectral behavior. A key objective is to understand how the underlying graph structure influences eigenvalue multiplicities and the geometry of their corresponding eigenspaces. This problem remains largely unresolved for many graph families and lies at the intersection of linear algebra, combinatorics, and the geometry of manifolds. Alongside advancing fundamental knowledge, the project emphasizes student training and mentorship, with a focus on broadening participation in the mathematical sciences through research opportunities, collaborative learning, and outreach. Ultimately, this work seeks to contribute both to open theoretical questions and to building an active and vibrant community of future mathematical scientists. 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.