THE RANK OF DILUTED RANDOM GRAPHS

• 成果类型: Article
• 署名作者: Bordenave, Charles; Lelarge, Marc; Salez, Justin
• 署名单位: Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Toulouse; Universite Toulouse III - Paul Sabatier; Universite Federale Toulouse Midi-Pyrenees (ComUE); Institut National des Sciences Appliquees de Toulouse; Universite de Toulouse; Universite Toulouse III - Paul Sabatier
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/10-AOP567
• 发表日期: 2011
• 页码: 1097-1121
• 关键词: model

摘要

We investigate the rank of the adjacency matrix of large diluted random graphs: for a sequence of graphs (G(n))(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 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 >= 0). Our proofs borrow ideas from analysis of algorithms, functional analysis, random matrix theory and statistical physics.