Top-k eigenvalue limit points of d-regular graphs

Conjecture 1.3 · arXiv:2304.01281

arXiv Conjecture high confidence— first stated 2023-10-13

Authors: Noga Alon, Fan Wei

Status solved high confidence

Conjecture 1.3 from arXiv:2304.01281 has been fully resolved by Dingding Dong and Theo McKenzie in December 2024. Their paper 'Arbitrary Spectral Edge of Regular Graphs' (arXiv:2412.09570) proves that for any d >= 3 and k >= 2, the set of all limit points of the vectors (lambda_1(G_i), ..., lambda_k(G_i)) for infinite sequences of d-regular graphs is exactly B(d,k) = {(mu_1,...,mu_k) : d = mu_1 >= ... >= mu_k >= 2sqrt(d-1)}, confirming the conjecture in full. The authors explicitly state that the k=2 case was due to Alon and Wei and that their result confirms the conjecture of theirs.

Cited literature (1)

proof Arbitrary Spectral Edge of Regular Graphs (2024)

Dingding Dong, Theo McKenzie · arXiv preprint · arXiv:2412.09570 · doi:10.48550/arXiv.2412.09570

Proves the full conjecture: for any d >= 3 and k >= 2, the set of limit points of the first k eigenvalues of d-regular graph sequences is exactly {(mu_1,...,mu_k) : d = mu_1 >= ... >= mu_k >= 2sqrt(d-1)}, confirming Conjecture 1.3 of Alon and Wei.

Reviewer notes. The resolving paper arXiv:2412.09570 was verified via WebFetch; it explicitly cites the k=2 result of Alon and Wei and confirms their conjecture for all k >= 2.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For any $d \geq 3$ and any fixed $k$, the set of all limit points of the vectors $(\lambda_1(G_i), \lambda_2(G_i), \ldots, \lambda_k(G_i))$ for an infinite sequence $G_i$ of $d$-regular graphs is exactly the set $$B(d,k) = \{(\mu_1, \mu_2, \ldots, \mu_k) : d = \mu_1 \geq \mu_2 \geq \mu_3 \geq \ldots \geq \mu_k \geq 2\sqrt{d-1}\}.$$

Context

Theorem 1.1 establishes the case $k=2$ (the set of limit points of $\lambda_2$ for $d$-regular graphs is $[2\sqrt{d-1}, d]$). The authors conjecture this extends to vectors of the top $k$ eigenvalues for any fixed $k$, noting that the containment $\subseteq B(d,k)$ is already known but they have not been able to prove that every point of $B(d,k)$ is a limit point even for $k=3$. Theorem 1.5 shows every point of a slightly smaller set (with $2\sqrt{d-1}$ replaced by $2\sqrt{d-1} + 1/\sqrt{d-1}$) is indeed a limit point of $d$-regular graph sequences.

Source paper

The limit points of the top and bottom eigenvalues of regular graphs
Noga Alon, Fan Wei · 2023-10-13
https://arxiv.org/abs/2304.01281 PDF source