Spectral gap and embedded trees for the Laplacian of the Erdős-Rényi graph

Abstract

For the Erdős-Rényi graph of size $N$ with mean degree $(1+o(1))\frac{\log N}{t+1}\le d\le (1-o(1))\frac{\log N}{t}$ where $t\in {\mathbb{N}}^{\ast }$, with high probability the smallest non zero eigenvalue of the Laplacian is equal to $2-2\cos (\pi (2t+1{)}^{-1})+o(1)$. This eigenvalue arises from a small subgraph isomorphic to a line of size $t$ linked to the giant connected component by only one edge.

22 pages, 4 figures

References in corpus (2)

• Poisson statistics and localization at the spectral edge of sparse Erdős-Rényi graphs
• Extreme eigenvalues of Laplacian random matrices with Gaussian entries