Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-23T02:43:48.507Z Has data issue: false hasContentIssue false
  • English
  • Français

Sparse random matrices: spectral edge and statistics of rooted trees

Part of: Graph theory Limit theorems

Published online by Cambridge University Press:  01 July 2016

A. Khorunzhy
A. Khorunzhy*
Affiliation:
Institute for Low Temperature Physics, Ukraine
*
∗ Current address: Faculté de Mathematiques, Université Paris 7–Denis Diderot, 2 Place Jussieu, Paris 75251 Cedex 05, France. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Following Füredi and Komlós, we develop a graph theory method to study the high moments of large random matrices with independent entries. We apply this method to sparse N × N random matrices AN,p that have, on average, p non-zero elements per row. One of our results is related to the asymptotic behaviour of the spectral norm ∥AN,p∥ in the limit 1 ≪ p ≪ N. We show that the value pc = log N is the critical one for lim ∥AN,p/√p∥ to be bounded or not. We discuss relations of this result with the Erdős–Rényi limit theorem and properties of large random graphs. In the proof, the principal issue is that the averaged vertex degree of plane rooted trees of k edges remains bounded even when k → ∞. This observation implies fairly precise estimates for the moments of AN,p. They lead to certain generalizations of the results by Sinai and Soshnikov on the universality of local spectral statistics at the border of the limiting spectra of large random matrices.

Keywords

random matricesspectral normuniversality conjectureuniversality conjecturerandom graphsErdos-Renyi partial sums

MSC classification

Primary: 60F99: None of the above, but in this section
Secondary: 05C05: Trees
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 33 , Issue 1 , March 2001 , pp. 124 - 140
Copyright
Copyright © Applied Probability Trust 2001 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Amit, D. J. (1989). Modeling Brain Function. Cambridge University Press.CrossRefGoogle Scholar
[2] Bai, Z. D. and Yin, Y. Q. (1988). Necessary and sufficient conditions for almost sure convergence of the largest eigenvalue of a Wigner matrix. Ann. Prob. 16, 1729–1741.Google Scholar
[3] Bollobas, B. (1985). Random Graphs. Academic Press, New York.Google Scholar
[4] Bovier, A. and Gayrard, V. (1993). Rigorous results on the thermodynamics of the dilute Hopfield model. J. Stat. Phys. 52, 59–112.Google Scholar
[5] Deift, P. A., Its, A. R. and Zhou, X. (1997). A Riemann–Hilbert approach to asymptotic problems arising in the theory of random matrix models and also in the theory of integrable statistical mechanics. Ann. Math. 146, 149–235.Google Scholar
[6] Erdős, P. and Rényi, A. (1950). On a new law of large numbers. J. Anal. Math. 23, 103–111.Google Scholar
[7] Evangelou, S. (1992). A numerical study of sparse random matrices. J. Stat. Phys. 69, 361–383.CrossRefGoogle Scholar
[8] Füredi, Z. and Komlós, J. (1981). The eigenvalues of random symmetric matrices. Combinatorica 1, 233–241.CrossRefGoogle Scholar
[9] Guhr, T., Müller-Groeling, A. and Weidenmüller, H. (1998). Random matrix theories in quantum physics: common concepts. Physics Rep. 299, 189–425.CrossRefGoogle Scholar
[10] Jakobson, D., Miller, S., Rivin, I. and Rudnick, Z. (1999). Level spacing for regular graphs. In Emerging Applications of Number Theory, eds Hejhal, D. A. et al. Springer, New York, pp. 317–327.Google Scholar
[11] Johansson, K. (1998). The longest increasing subsequence in a random permutation and a unitary random matrix model. Math. Res. Lett. 5, 63–83.CrossRefGoogle Scholar
[12] Khorunzhy, A. and Rodgers, G. J. (1998). On the Wigner law in dilute random matrices. Rep. Math. Phys. 43, 237–319.Google Scholar
[13] Khorunzhy, A., Khoruzhenko, B., Pastur, L. and Shcherbina, M. (1992). Large-n limit in statistical mechanics and the spectral theory of disordered systems. In Phase Transitions and Critical Phenomena, Vol. 15, eds Domb, C. and Lebowitz, J. L.. Academic Press, London, pp. 53–245.Google Scholar
[14] Mirlin, A. D. and Fyodorov, Y. V. (1991). Universality of level correlation function of sparse random matrices. J. Phys. A 24, 2273–2286.CrossRefGoogle Scholar
[15] Riordan, J. (1968). Combinatorial Identities. John Wiley, New York.Google Scholar
[16] Rodgers, G. J. and Bray, A. J. (1988). Density of states of a sparse random matrix. Phys. Rev. B 37, 3557–3562.CrossRefGoogle ScholarPubMed
[17] Sinai, Ya. G. and Soshnikov, A. (1998). A refinement of Wigner's semicircle law in a neighborhood of the spectrum edge for random symmetric matrices. Funktsional. Anal. i Prilozhen. 32, 56–79 (in Russian). English translation: Funct. Anal. Appl. 32, 114–131.CrossRefGoogle Scholar
[18] Soshnikov, A. (1999). Universality at the edge of the spectrum in Wigner random matrices. Commun. Math. Phys. 207, 697–733.Google Scholar
[19] Wigner, E. (1955). Characteristic vectors of bordered matrices with infinite dimensions. Ann. Math. 62, 548–564.Google Scholar
[20] Zvonkin, A. (1997). Matrix integrals and map enumeration. Math. Comput. Modell. 26, 281–304.Google Scholar