Optimal Eigenvalue Rigidity of Random Regular Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916252618850304 |
|---|---|
| author | Huang, Jiaoyang McKenzie, Theo Yau, Horng-Tzer |
| author_facet | Huang, Jiaoyang McKenzie, Theo Yau, Horng-Tzer |
| contents | Consider the normalized adjacency matrices of random $d$-regular graphs on $N$ vertices with fixed degree $d\geq 3$, and denote the eigenvalues as $λ_1=d/\sqrt{d-1}\geq λ_2\geqλ_3\cdots\geq λ_N$. We prove that the optimal (up to an extra $N^{{\rm o}_N(1)}$ factor, where ${\rm o}_N(1)$ can be arbitrarily small) eigenvalue rigidity holds. More precisely, denote $γ_i$ as the classical location of the $i$-th eigenvalue under the Kesten-Mckay law in decreasing order. Then with probability $1-N^{-1+{\rm o}_N(1)}$,
\begin{align*}
|λ_i-γ_i|\leq \frac{N^{{\rm o}_N(1)}}{N^{2/3} (\min\{i,N-i+1\})^{1/3}},\quad \text{ for all } i\in \{2,3,\cdots,N\}.
\end{align*}
In particular, the fluctuations of extreme eigenvalues are bounded by $N^{-2/3+{\rm o}_N(1)}$. This gives the same order of fluctuation as for the eigenvalues of matrices from the Gaussian Orthogonal Ensemble. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_12161 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimal Eigenvalue Rigidity of Random Regular Graphs Huang, Jiaoyang McKenzie, Theo Yau, Horng-Tzer Probability 60B20, 05C80 Consider the normalized adjacency matrices of random $d$-regular graphs on $N$ vertices with fixed degree $d\geq 3$, and denote the eigenvalues as $λ_1=d/\sqrt{d-1}\geq λ_2\geqλ_3\cdots\geq λ_N$. We prove that the optimal (up to an extra $N^{{\rm o}_N(1)}$ factor, where ${\rm o}_N(1)$ can be arbitrarily small) eigenvalue rigidity holds. More precisely, denote $γ_i$ as the classical location of the $i$-th eigenvalue under the Kesten-Mckay law in decreasing order. Then with probability $1-N^{-1+{\rm o}_N(1)}$, \begin{align*} |λ_i-γ_i|\leq \frac{N^{{\rm o}_N(1)}}{N^{2/3} (\min\{i,N-i+1\})^{1/3}},\quad \text{ for all } i\in \{2,3,\cdots,N\}. \end{align*} In particular, the fluctuations of extreme eigenvalues are bounded by $N^{-2/3+{\rm o}_N(1)}$. This gives the same order of fluctuation as for the eigenvalues of matrices from the Gaussian Orthogonal Ensemble. |
| title | Optimal Eigenvalue Rigidity of Random Regular Graphs |
| topic | Probability 60B20, 05C80 |
| url | https://arxiv.org/abs/2405.12161 |