Spectral convergence of random regular graphs: Chebyshev polynomials, non-backtracking walks, and unitary-color extensions
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917801632989184 |
|---|---|
| author | Gong, Yulin Li, Wenbo Liu, Shiping |
| author_facet | Gong, Yulin Li, Wenbo Liu, Shiping |
| contents | In this paper, we give a short proof of the weak convergence to the Kesten-McKay distribution for the normalized spectral measures of random $N$-lifts. This result is derived by generalizing a formula of Friedman involving Chebyshev polynomials and non-backtracking walks. We also 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 $(q_n+1)$-regular graphs $G_n$ with $n$ vertices, if $q_n = n^{o(1)}$ and $q_n$ tends to infinity, the normalized spectral measure converges almost surely in $p$-Wasserstein distance to the semicircle distribution for any $p \in [1, \infty)$. This strengthens a result of Dumitriu and Pal. Many of the results are extended to unitary-colored regular graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_05759 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Spectral convergence of random regular graphs: Chebyshev polynomials, non-backtracking walks, and unitary-color extensions Gong, Yulin Li, Wenbo Liu, Shiping Combinatorics Probability Spectral Theory 05C31, 05C50, 05C80, 60B20 In this paper, we give a short proof of the weak convergence to the Kesten-McKay distribution for the normalized spectral measures of random $N$-lifts. This result is derived by generalizing a formula of Friedman involving Chebyshev polynomials and non-backtracking walks. We also 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 $(q_n+1)$-regular graphs $G_n$ with $n$ vertices, if $q_n = n^{o(1)}$ and $q_n$ tends to infinity, the normalized spectral measure converges almost surely in $p$-Wasserstein distance to the semicircle distribution for any $p \in [1, \infty)$. This strengthens a result of Dumitriu and Pal. Many of the results are extended to unitary-colored regular graphs. |
| title | Spectral convergence of random regular graphs: Chebyshev polynomials, non-backtracking walks, and unitary-color extensions |
| topic | Combinatorics Probability Spectral Theory 05C31, 05C50, 05C80, 60B20 |
| url | https://arxiv.org/abs/2406.05759 |