The rank of diluted random graphs

Abstract

We investigate the rank of the adjacency matrix of large diluted random graphs: for a sequence of graphs $(G_n{)}_{n\ge 0}$ converging locally to a Galton--Watson tree $T$ (GWT), we provide an explicit formula for the asymptotic multiplicity of the eigenvalue 0 in terms of the degree generating function ${\varphi }_{\ast }$ of $T$. In the first part, we show that the adjacency operator associated with $T$ is always self-adjoint; we analyze the associated spectral measure at the root and characterize the distribution of its atomic mass at 0. In the second part, we establish a sufficient condition on ${\varphi }_{\ast }$ for the expectation of this atomic mass to be precisely the normalized limit of the dimension of the kernel of the adjacency matrices of $(G_n{)}_{n\ge 0}$. Our proofs borrow ideas from analysis of algorithms, functional analysis, random matrix theory and statistical physics.

Published in at http://dx.doi.org/10.1214/10-AOP567 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Cited by in corpus (7)

• Spectrum of non-Hermitian heavy tailed random matrices
• A large deviation principle for Wigner matrices without Gaussian tails
• Lifshitz tails on the Bethe lattice: a combinatorial approach
• Disentangling Giant Component and Finite Cluster Contributions in Sparse Matrix Spectra
• Spectra of large diluted but bushy random graphs
• On quantum percolation in finite regular graphs
• Bridging Classical and Quantum Information Scrambling with the Operator Entanglement Spectrum