Spectral convergence of random regular graphs: Chebyshev polynomials, non‐backtracking walks, and unitary‐color extensions

Yulin Gong, Wenbo Li and Shiping Liu

Mathematische Nachrichten, 2025, vol. 298, issue 10, 3417-3439

Abstract: In this paper, we extend a criterion of Sodin on the convergence of graph spectral measures to regular graphs of growing degree. As a result, we show that for a sequence of random (qn+1)$(q_n+1)$‐regular graphs Gn$G_n$ with n$n$ vertices, if qn=no(1)$q_n = n^{o(1)}$ and qn$q_n$ tends to infinity, the normalized spectral measure converges almost surely in p$p$‐Wasserstein distance to the semicircle distribution for any p∈[1,∞)$p \in [1, \infty)$. This strengthens a result of Dumitriu and Pal. Many of the results are also extended to unitary‐colored regular graphs. For example, we give a short proof of the weak convergence to the Kesten–McKay distribution for the normalized spectral measures of random N$N$‐lifts. This result is derived by generalizing a formula of Friedman involving Chebyshev polynomials and non‐backtracking walks.

Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/mana.70046

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bla:mathna:v:298:y:2025:i:10:p:3417-3439

Ordering information: This journal article can be ordered from
http://www.blackwell ... bs.asp?ref=0025-584X

Access Statistics for this article

Mathematische Nachrichten is currently edited by Robert Denk

More articles in Mathematische Nachrichten from Wiley Blackwell
Bibliographic data for series maintained by Wiley Content Delivery ().