×

The rank of diluted random graphs. (English) Zbl 1298.05283

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

MSC:

05C80 Random graphs (graph-theoretic aspects)
15B52 Random matrices (algebraic aspects)
47A10 Spectrum, resolvent
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Aizenman, M., Sims, R. and Warzel, S. (2006). Stability of the absolutely continuous spectrum of random Schrödinger operators on tree graphs. Probab. Theory Related Fields 136 363-394. · Zbl 1169.82007
[2] Aldous, D. and Lyons, R. (2007). Processes on unimodular random networks. Electron. J. Probab. 12 1454-1508. · Zbl 1131.60003
[3] Aldous, D. and Steele, J. M. (2004). The objective method: Probabilistic combinatorial optimization and local weak convergence. In Probability on Discrete Structures. Encyclopaedia Math. Sci. 110 1-72. Springer, Berlin. · Zbl 1037.60008
[4] Bai, Z. D. and Silverstein, J. W. (2006). Spectral Analysis of Large Dimensional Random Matrices. Mathematics Monograph Series 2 . Science Press, Beijing. · Zbl 1196.60002
[5] Bauer, M. and Golinelli, O. (2000). On the kernel of tree incidence matrices. J. Integer Seq. 3 Art. 00.1.4, 1 HTML document (electronic). · Zbl 0960.05068
[6] Bauer, M. and Golinelli, O. (2001). Exactly solvable model with two conductor-insulator transitions driven by impurities. Phys. Rev. Lett. 86 2621-2624.
[7] Benjamini, I. and Schramm, O. (2001). Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 13 pp. (electronic). · Zbl 1010.82021
[8] Bhanidi, S., Evans, S. N. and Sen, A. (2009). Spectra of large random trees. · Zbl 1168.15017
[9] Bohman, T. and Frieze, A. (2010). Karp-Sipser on random graphs with a fixed degree sequence. · Zbl 1234.05205
[10] Bordenave, C. and Lelarge, M. (2010). Resolvent of large random graphs. Random Structures and Algorithms 37 332-352. · Zbl 1209.05222
[11] Bordenave, C., Lelarge, M. and Salez, J. (2010). Matchings on infinite graphs. · Zbl 1278.60018
[12] Costello, K. P. and Vu, V. H. (2008). The rank of random graphs. Random Structures Algorithms 33 269-285. · Zbl 1194.05083
[13] Costello, K. P., Tao, T. and Vu, V. (2006). Random symmetric matrices are almost surely nonsingular. Duke Math. J. 135 395-413. · Zbl 1110.15020
[14] Cvetković, D. M., Doob, M. and Sachs, H. (1995). Spectra of Graphs : Theory and Applications , 3rd ed. Johann Ambrosius Barth, Heidelberg. · Zbl 0824.05046
[15] Karp, R. and Sipser, M. (1981). Maximum matchings in sparse random graphs. In Proc. of the Twenty-Second IEEE Annual Symposium on Foundations of Computer Science 364-375. IEEE Computer Soc., Los Angeles, CA.
[16] Khorunzhy, O., Shcherbina, M. and Vengerovsky, V. (2004). Eigenvalue distribution of large weighted random graphs. J. Math. Phys. 45 1648-1672. · Zbl 1068.05062
[17] Klein, A. (1998). Extended states in the Anderson model on the Bethe lattice. Adv. Math. 133 163-184. · Zbl 0899.60088
[18] Reed, M. and Simon, B. (1972). Methods of Modern Mathematical Physics. I. Functional Analysis . Academic Press, New York. · Zbl 0459.46001
[19] Zdeborová, L. and Mézard, M. (2006). The number of matchings in random graphs. J. Stat. Mech. Theory Exp. 5 P05003, 24 pp. (electronic).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.