The limit points of the top and bottom eigenvalues of regular graphs

Noga Alon, Wei FanarXiv 2023 · DOI · arXiv

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

Abstract

We prove that for each $d \geq 3$ the set of all limit points of the second largest eigenvalue of growing sequences of $d$-regular graphs is $[2\sqrt{d-1},d]$. A similar argument shows that the set of all limit points of the smallest eigenvalue of growing sequences of $d$-regular graphs with growing (odd) girth is $[-d, -2 \sqrt{d-1}]$. The more general question of identifying all vectors which are limit points of the vectors of the top $k$ eigenvalues of sequences of $d$-regular graphs is considered as well. As a by product, in the study of discrete counterpart of the "scarring" phenomenon observed in the investigation of quantum ergodicity on manifolds, our technique provides a method to construct $d$-regular almost Ramanujan graphs with large girth and localized eigenvectors corresponding to eigenvalues larger than $2\sqrt{d-1}$, strengthening a result of Alon, Ganguly, and Srivastava.
BibTeX
@misc{alon2023limit,
  author = {Noga Alon and Wei Fan},
  title = {{The limit points of the top and bottom eigenvalues of regular graphs}},
  year = {2023},
  eprint = {2304.01281},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2304.01281},
}

Loading related content...

Figure