We investigate the rank of the adjacency matrix of large diluted random graphs: for a sequence of graphs (Gn)n≥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 φ∗ 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 φ∗ for the expectation of this atomic mass to be precisely the normalized limit of the dimension of the kernel of the adjacency matrices of (Gn)n≥0. Our proofs borrow ideas from analysis of algorithms, functional analysis, random matrix theory and statistical physics.
Publié le : 2011-05-15
Classification:
Random graphs,
adjacency matrix,
random matrices,
local weak convergence,
Karp and Sipser algorithm,
05C80,
15A52,
47A10
@article{1300281733,
author = {Bordenave, Charles and Lelarge, Marc and Salez, Justin},
title = {The rank of diluted random graphs},
journal = {Ann. Probab.},
volume = {39},
number = {1},
year = {2011},
pages = { 1097-1121},
language = {en},
url = {http://dml.mathdoc.fr/item/1300281733}
}
Bordenave, Charles; Lelarge, Marc; Salez, Justin. The rank of diluted random graphs. Ann. Probab., Tome 39 (2011) no. 1, pp. 1097-1121. http://gdmltest.u-ga.fr/item/1300281733/