On Concentration Inequality of the Laplacian Matrix of Erdős-Rényi Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916597365473280 |
|---|---|
| author | Chen, Yiming Hu, Xuanang Li, Pengtao |
| author_facet | Chen, Yiming Hu, Xuanang Li, Pengtao |
| contents | This paper focuses on the concentration properties of the spectral norm of the normalized Laplacian matrix for Erdős-Rényi random graphs. First, We achieve the optimal bound that can be attained in the further question posed by Le et al. [24] for the regularized Laplacian matrix. Beyond that, we also establish a uniform concentration inequality for the spectral norm of the Laplacian matrix in the homogeneous case, relying on a key tool: the uniform concentration property of degrees, which may be of independent interest. Additionally, we prove that after normalizing the eigenvector corresponding to the largest eigenvalue, the spectral norm of the Laplacian matrix concentrates around 1, which may be useful in special cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_02248 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Concentration Inequality of the Laplacian Matrix of Erdős-Rényi Graphs Chen, Yiming Hu, Xuanang Li, Pengtao Probability 60E15, 60B20 This paper focuses on the concentration properties of the spectral norm of the normalized Laplacian matrix for Erdős-Rényi random graphs. First, We achieve the optimal bound that can be attained in the further question posed by Le et al. [24] for the regularized Laplacian matrix. Beyond that, we also establish a uniform concentration inequality for the spectral norm of the Laplacian matrix in the homogeneous case, relying on a key tool: the uniform concentration property of degrees, which may be of independent interest. Additionally, we prove that after normalizing the eigenvector corresponding to the largest eigenvalue, the spectral norm of the Laplacian matrix concentrates around 1, which may be useful in special cases. |
| title | On Concentration Inequality of the Laplacian Matrix of Erdős-Rényi Graphs |
| topic | Probability 60E15, 60B20 |
| url | https://arxiv.org/abs/2502.02248 |