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

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 ‐regular graphs with vertices, if and tends to infinity, the normalized spectral measure converges almost surely in ‐Wasserstein distance to the semicircle distribution for any . 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 ‐lifts. This result is derived by generalizing a formula of Friedman involving Chebyshev polynomials and non‐backtracking walks.