Abstract
This paper investigates the spectral properties of $d$-regular graphs as the number of vertices $n$ tends to infinity. We demonstrate that for any $d \geq 3$, the set of limit points of the second largest eigenvalue $\lambda_2$ is the entire interval $[2\sqrt{d-1}, d]$. Furthermore, for sequences of $d$-regular graphs with growing odd girth, the limit points of the smallest eigenvalue $\lambda_n$ fill the interval $[-d, -2\sqrt{d-1}]$. We also explore the joint limit points of the top $k$ eigenvalues and provide a construction for "almost Ramanujan" graphs exhibiting discrete scarring—localized eigenvectors corresponding to eigenvalues exceeding the Alon-Boppana bound.
Introduction
In spectral graph theory, the eigenvalues of the adjacency matrix of a graph provide deep insights into its combinatorial and structural properties. For a $d$-regular graph, the largest eigenvalue $\lambda_1$ is always $d$, associated with the constant eigenvector. The second-largest eigenvalue, $\lambda_2$, is of particular interest as it dictates the expansion properties, mixing time of random walks, and overall connectivity of the graph.
The Alon-Boppana bound establishes that for any sequence of $d$-regular graphs where the number of vertices $n \to \infty$, the second eigenvalue satisfies $\liminf_{n \to \infty} \lambda_2 \geq 2\sqrt{d-1}$. Graphs that asymptotically meet this lower bound are known as Ramanujan graphs, representing the theoretical limit of spectral expansion. A long-standing question, suggested by Peter Sarnak, asks whether the possible values of $\lambda_2$ for large $n$ are dense across the entire range from the Ramanujan bound to the maximum possible value $d$. This research confirms that there are no gaps in this spectrum.
Methodology
The authors employ a dual-engine approach combining probabilistic constructions with deterministic perturbations to map the interval of limit points.
1. Local Swaps and Eigenvector Non-localization
To prove that the interval $[2\sqrt{d-1}, d]$ is fully covered, the study utilizes the concept of "local swaps." Starting with a high-girth Ramanujan graph (where $\lambda_2 \approx 2\sqrt{d-1}$), the authors perform edge swaps—deleting two edges and adding two new ones to maintain $d$-regularity.
The success of this method hinges on the "non-localization" of eigenvectors in high-girth graphs. Because the eigenvectors are spread across many vertices rather than concentrated on a few, a local change to the graph's edge set results in an infinitesimally small shift in the eigenvalue. By performing a sequence of these swaps, the authors can effectively "walk" the eigenvalue $\lambda_2$ across the interval in nearly continuous increments, ensuring that every value in $[2\sqrt{d-1}, d]$ is a limit point.
2. Patching Gadgets
To address more complex spectral requirements, such as controlling the top $k$ eigenvalues simultaneously or inducing specific localization properties, the authors introduce "patching gadgets." This involves taking a large base graph with known spectral properties and "patching" in smaller, carefully designed gadget graphs. By adjusting the structure of these gadgets and their attachment points, the authors can precisely "pull" specific eigenvalues to target levels without destabilizing the rest of the graph's spectrum.
Key Results
Theorem 1.1: The $\lambda_2$ Interval
For any fixed $d \geq 3$, the set of all limit points of the second largest eigenvalue of sequences of $d$-regular graphs is exactly the interval $[2\sqrt{d-1}, d]$.
Theorem 1.2: The Smallest Eigenvalue
When considering the smallest eigenvalue $\lambda_n$, the behavior is symmetric if we impose a growing (odd) girth requirement. The set of limit points for $\lambda_n$ in such sequences is $[-d, -2\sqrt{d-1}]$. Without the girth requirement, the landscape is significantly more complex and remains an area for future study.
Theorem 1.5 & 1.6: Top $k$ Eigenvalues and Discrete Scarring
The paper extends these findings to the top $k$ eigenvalues, showing they can be controlled to reach nearly any point in the valid multidimensional space. Additionally, the authors provide a method to construct $d$-regular almost Ramanujan graphs that exhibit "discrete scarring." This phenomenon, borrowed from quantum chaos, describes eigenvectors that concentrate their mass on a small set of vertices (periodic orbits) rather than distributing evenly. This result strengthens previous work by Alon, Ganguly, and Srivastava by demonstrating that such scars can exist even in graphs with very large girth.
Discussion and Future Work
This research bridges the gap between discrete combinatorics and continuous analysis, showing that the limit points of discrete graph sequences can form continuous intervals. While the paper provides a near-complete picture for $\lambda_2$ and the top $k$ eigenvalues, a small gap remains in the characterization of the top $k$ eigenvalues near the $2\sqrt{d-1}$ boundary for $k \geq 3$ (Conjecture 1.3).
Furthermore, the study of the smallest eigenvalue $\lambda_n$ without the growing girth assumption suggests a much more intricate set of limit points, likely containing isolated values. Understanding this "bottom" of the spectrum remains a significant challenge for the field.
Summary updated