%0 Journal Article
%T The rank of diluted random graphs
%A Charles Bordenave
%A Marc Lelarge
%A Justin Salez
%J Mathematics
%D 2009
%I arXiv
%R 10.1214/10-AOP567
%X We investigate the rank of the adjacency matrix of large diluted random graphs: for a sequence of graphs $(G_n)_{n\geq0}$ 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 $\phi_*$ 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 $\phi_*$ 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\geq 0}$. Our proofs borrow ideas from analysis of algorithms, functional analysis, random matrix theory and statistical physics.
%U http://arxiv.org/abs/0907.4244v4