2023/11/13 by Matthew B. Crawford, David J. Marchette, Crawford, Matthew B. +5
Computer Science · Mathematics · #05C75 (Primary) 60B20 #05C80 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Matrix Theory and Algorithms #Spectral Theory (math.SP) #Spectral Theory in Mathematical Physics
paper · pdf · doi:10.48550/arxiv.2311.07675
openalex publication_date 2023/11/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We define a graph to be S-regular if it contains an equitable partition given by a matrix S. These graphs are generalizations of both regular and bipartite, biregular graphs. An S-regular matrix is defined then as a matrix on an S-regular graph consistent with the graph's equitable partition. In this paper we derive the limiting spectral density for large, random S-regular matrices as well as limiting functions of certain statistics for their eigenvector coordinates as a function of eigenvalue. These limiting functions are defined in terms of spectral measures on S-regular trees. In general, these spectral measures do not have a closed-form expression; however, we provide a defining system of polynomials for them. Finally, we explore eigenvalue bounds of S-regular graph, proving an expander mixing lemma, Alon-Bopana bound, and other eigenvalue inequalities in terms of the eigenvalues of the matrix S.