Skip to main content
SpringerLink
Log in

Spectra of Large Random Trees

  • Published:
Journal of Theoretical Probability Aims and scope Submit manuscript

Abstract

We analyze the eigenvalues of the adjacency matrices of a wide variety of random trees. Using general, broadly applicable arguments based on the interlacing inequalities for the eigenvalues of a principal submatrix of a Hermitian matrix and a suitable notion of local weak convergence for an ensemble of random trees that we call probability fringe convergence, we show that the empirical spectral distributions for many random tree models converge to a deterministic (model-dependent) limit as the number of vertices goes to infinity.

Moreover, the masses assigned by the empirical spectral distributions to individual points also converge in distribution to constants. We conclude for ensembles such as the linear preferential attachment models, random recursive trees, and the uniform random trees that the limiting spectral distribution has a set of atoms that is dense in the real line. We obtain lower bounds on the mass assigned to zero by the empirical spectral measures via the connection between the number of zero eigenvalues of the adjacency matrix of a tree and the cardinality of a maximal matching on the tree. In particular, we employ a simplified version of an algorithm due to Karp and Sipser to construct maximal matchings and understand their properties. Moreover, we show that the total weight of a weighted matching is asymptotically equivalent to a constant multiple of the number of vertices when the edge weights are independent, identically distributed, nonnegative random variables with finite expected value, thereby significantly extending a result obtained by Aldous and Steele in the special case of uniform random trees.

We greatly generalize a celebrated result obtained by Schwenk for the uniform random trees by showing that if any ensemble converges in the probability fringe sense and a very mild further condition holds, then, with probability converging to one, the spectrum of a realization is shared by at least one other (nonisomorphic) tree.

For the linear preferential attachment model with parameter a>−1, we show that for any fixed k, the k largest eigenvalues jointly converge in distribution to a nontrivial limit when rescaled by \(n^{1/2\gamma_{a}}\), where γ a =a+2 is the Malthusian rate of growth parameter for an associated continuous-time branching process.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aldous, D.: Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1(2), 228–266 (1991). MR MR1102319 (92j:60009)

    Article  MathSciNet  MATH  Google Scholar 

  2. Aldous, D.: The continuum random tree. I. Ann. Probab. 19(1), 1–28 (1991). MR MR1085326 (91i:60024)

    Article  MathSciNet  MATH  Google Scholar 

  3. Aldous, D., Steele, J.M.: The objective method: probabilistic combinatorial optimization and local weak convergence. In: Probability on Discrete Structures. Encyclopaedia Math. Sci., vol. 110, pp. 1–72. Springer, Berlin (2004). MR MR2023650 (2005e:60018)

    Google Scholar 

  4. Bai, Z., Silverstein, J.: Convergence rate of expected spectral distributions of large random matrices. Part I. Wigner matrices. Ann. Appl. Probab. 21(2), 625–648 (1993)

    MATH  Google Scholar 

  5. Bauer, M., Golinelli, O.: On the kernel of tree incidence matrices. J. Integer Seq. 3(1), Article 00.1.4 (2000). 1 HTML document (electronic). MR MR1750745 (2001b:05138)

  6. Bauer, M., Golinelli, O.: Random incidence matrices: moments of the spectral density. J. Stat. Phys. 103(1), 301–337 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  7. Bhamidi, S.: Universal techniques for preferential attachment: local and global analysis (2007). Preprint available at http://www.stat.berkeley.edu/users/shanky/preferent.pdf

  8. Bleher, P., Its, A. (eds.): Random Matrix Models and Their Applications. Mathematical Sciences Research Institute Publications, vol. 40. Cambridge University Press, Cambridge (2001). MR MR1842779 (2002a:82002)

    MATH  Google Scholar 

  9. Biggs, N.: Algebraic Graph Theory, 2nd edn. Cambridge Mathematical Library, Cambridge University Press, Cambridge (1993). MR MR1271140 (95h:05105)

    Google Scholar 

  10. Bordenave, C., Lelarge, M.: Resolvent of large random graphs. Random Struct. Algorithms 37(3), 332–352 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  11. Bordenave, C., Lelarge, M.: The rank of diluted random graphs (2009). arXiv:0907.4244

  12. Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. American Elsevier Publishing Co., Inc., New York (1976). MR MR0411988 (54 #117)

    MATH  Google Scholar 

  13. Botti, P., Merris, R.: Almost all trees share a complete set of immanantal polynomials. J. Graph Theory 17(4), 467–476 (1993). MR MR1231010 (94g:05053)

    Article  MathSciNet  MATH  Google Scholar 

  14. Bollobás, B., Nikiforov, V.: Graphs and Hermitian matrices: eigenvalue interlacing. Discrete Math. 289(1–3), 119–127 (2004). MR MR2106034 (2005j:05058)

    Article  MathSciNet  MATH  Google Scholar 

  15. Bollobás, B., Riordan, O.M.: Mathematical results on scale-free random graphs. In: Handbook of Graphs and Networks, pp. 1–34. Wiley-VCH, Weinheim (2003). MR MR2016117 (2004j:05108)

    Google Scholar 

  16. Cvetković, D.M., Doob, M., Gutman, I., Torgašev, A.: Recent Results in the Theory of Graph Spectra. Annals of Discrete Mathematics, vol. 36. North-Holland, Amsterdam (1988). MR MR926481 (89d:05130)

    MATH  Google Scholar 

  17. Cvetković, D.M., Doob, M., Sachs, H.: Spectra of Graphs, 3rd edn. Johann Ambrosius Barth, Heidelberg (1995). Theory and applications. MR MR1324340 (96b:05108)

    MATH  Google Scholar 

  18. Chung, F.R.K.: Spectral Graph Theory. CBMS Regional Conference Series in Mathematics, vol. 92 (1997). Published for the Conference Board of the Mathematical Sciences, Washington, DC. MR MR1421568 (97k:58183)

    MATH  Google Scholar 

  19. Chung, F., Lu, L., Vu, V.: Eigenvalues of random power law graphs. Ann. Comb. 7(1), 21–33 (2003)

    MathSciNet  MATH  Google Scholar 

  20. Chung, F., Lu, L., Vu, V.: Spectra of random graphs with given expected degrees. Proc. Nat. Acad. Sci. 100(11), 6313–6318 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  21. Cvetković, D., Rowlinson, P., Simić, S.: Eigenspaces of Graphs. Encyclopedia of Mathematics and Its Applications, vol. 66. Cambridge University Press, Cambridge (1997). MR MR1440854 (98f:05111)

    Book  MATH  Google Scholar 

  22. Deift, P.A.: Orthogonal Polynomials and Random Matrices: A Riemann–Hilbert Approach. Courant Lecture Notes in Mathematics, vol. 3. New York University Courant Institute of Mathematical Sciences, New York (1999). MR MR1677884 (2000g:47048)

    Google Scholar 

  23. Durrett, R.: Random Graph Dynamics, Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge (2007). MR MR2271734

    Google Scholar 

  24. Flaxman, A., Frieze, A., Fenner, T.: High degree vertices and eigenvalues in the preferential attachment graph. In: Approximation, Randomization, and Combinatorial Optimization. Lecture Notes in Comput. Sci., vol. 2764, pp. 264–274. Springer, Berlin (2003). MR MR2080798 (2005e:05124)

    Google Scholar 

  25. Flaxman, A., Frieze, A., Fenner, T.: High degree vertices and eigenvalues in the preferential attachment graph. Internet Math. 2(1), 1–19 (2005). MR MR2166274 (2006e:05157)

    Article  MathSciNet  MATH  Google Scholar 

  26. Fiol, M.A.: Eigenvalue interlacing and weight parameters of graphs. Linear Algebra Appl. 290(1–3), 275–301 (1999). MR MR1673001 (2000c:05100)

    Article  MathSciNet  MATH  Google Scholar 

  27. Forrester, P.J.: Log-gases and Random Matrices. London Mathematical Society Monographs Series, vol. 34. Princeton University Press, Princeton (2010), pp. xiv+791, ISBN 978-0-691-12829-0

    MATH  Google Scholar 

  28. Godsil, C., Royle, G.: Algebraic Graph Theory. Graduate Texts in Mathematics, vol. 207. Springer, New York (2001). MR MR1829620 (2002f:05002)

    Book  MATH  Google Scholar 

  29. Grimmett, G.R.: Random labelled trees and their branching networks. J. Aust. Math. Soc. Ser. A 30(2), 229–237 (1980/1981). MR MR607933 (82g:05042)

    Article  MathSciNet  Google Scholar 

  30. Guionnet, A.: Large Random Matrices: Lectures on Macroscopic Asymptotics: École d’Été de Probabilités de Saint-Flour XXXVI 2006. Lecture Notes in Mathematics. Springer, Berlin (2009)

    Book  MATH  Google Scholar 

  31. Haemers, W.H.: Interlacing eigenvalues and graphs. Linear Algebra Appl. 226/228, 593–616 (1995). MR MR1344588 (96e:05110)

    Article  MathSciNet  Google Scholar 

  32. Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1990). Corrected reprint of the 1985 original. MR MR1084815 (91i:15001)

    MATH  Google Scholar 

  33. Jagers, P.: General branching processes as Markov fields. Stoch. Process. Appl. 32(2), 183–212 (1989). MR MR1014449 (91d:60208)

    Article  MathSciNet  MATH  Google Scholar 

  34. Jagers, P., Nerman, O.: The growth and composition of branching populations. Adv. Appl. Probab. 16(2), 221–259 (1984). MR MR742953 (86j:60193)

    Article  MathSciNet  MATH  Google Scholar 

  35. Karp, R., Sipser, M.: Maximum matchings in sparse random graphs. In: 22nd Annual Symposium on Foundations of Computer Science, pp. 364–375 (1981)

    Google Scholar 

  36. Matsen, F.A., Evans, S.N.: Ubiquity of synonymity: almost all large binary trees are not uniquely identified by their spectra or their immanantal polynomials. U.C. Berkeley Department of Statistics Technical Report No. 698 (2006)

  37. Mehta, M.L.: Random Matrices, 3rd edn. Pure and Applied Mathematics (Amsterdam), vol. 142. Elsevier/Academic Press, Amsterdam (2004). MR MR2129906 (2006b:82001)

    MATH  Google Scholar 

  38. Móri, T.F.: The maximum degree of the Barabási–Albert random tree. Comb. Probab. Comput. 14(3), 339–348 (2005). MR MR2138118 (2006a:60014)

    Article  MATH  Google Scholar 

  39. Nerman, O., Jagers, P.: The stable double infinite pedigree process of supercritical branching populations. Z. Wahrscheinlichkeitstheor. Verw. Geb. 65(3), 445–460 (1984). MR MR731231 (85e:60091)

    Article  MathSciNet  MATH  Google Scholar 

  40. Norris, J.R.: Markov Chains. Cambridge Series in Statistical and Probabilistic Mathematics, vol. 2. Cambridge University Press, Cambridge (1998), pp. xvi+237, ISBN 0-521-48181-3. Reprint of 1997 original

    MATH  Google Scholar 

  41. Rojo, O.: On the spectra of certain rooted trees. Linear Algebra Appl. 414(1), 218–243 (2006). MR MR2209241 (2006m:05156)

    Article  MathSciNet  MATH  Google Scholar 

  42. Rojo, O.: The spectra of some trees and bounds for the largest eigenvalue of any tree. Linear Algebra Appl. 414(1), 199–217 (2006). MR MR2209240 (2007j:05145)

    Article  MathSciNet  MATH  Google Scholar 

  43. Rojo, O.: The spectra of a graph obtained from copies of a generalized Bethe tree. Linear Algebra Appl. 420(2–3), 490–507 (2007). MR MR2278225 (2007g:05116)

    Article  MathSciNet  MATH  Google Scholar 

  44. Rojo, O.: Spectra of weighted generalized Bethe trees joined at the root. Linear Algebra Appl. 428(11–12), 2961–2979 (2008). MR MR2416602

    Article  MathSciNet  MATH  Google Scholar 

  45. Rojo, O., Robbiano, M.: An explicit formula for eigenvalues of Bethe trees and upper bounds on the largest eigenvalue of any tree. Linear Algebra Appl. 427(1), 138–150 (2007). MR MR2353161 (2008g:05131)

    Article  MathSciNet  MATH  Google Scholar 

  46. Rojo, O., Robbiano, M.: On the spectra of some weighted rooted trees and applications. Linear Algebra Appl. 420(2–3), 310–328 (2007). MR MR2278210 (2007i:05118)

    Article  MathSciNet  MATH  Google Scholar 

  47. Rojo, O., Soto, R.: The spectra of the adjacency matrix and Laplacian matrix for some balanced trees. Linear Algebra Appl. 403, 97–117 (2005). MR MR2140275 (2006b:05081)

    Article  MathSciNet  MATH  Google Scholar 

  48. Rudas, A., Tóth, B., Valkó, B.: Random trees and general branching processes. Random Struct. Algorithms 31(2), 186–202 (2007). MR MR2343718

    Article  MATH  Google Scholar 

  49. Schwenk, A.J.: Almost all trees are cospectral. In: New Directions in the Theory of Graphs, Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971, pp. 275–307. Academic Press, New York (1973). MR MR0384582 (52 #5456)

    Google Scholar 

  50. Smythe, R.T., Mahmoud, H.M.: A survey of recursive trees. Teor. Imovir. Mat. Stat. 51, 1–29 (1994). MR MR1445048 (97k:60027)

    MATH  Google Scholar 

  51. Tulino, M., Verdu, S.: Random matrix theory and wireless communications. In: Foundations and Trends in Communications and Information Theory. Now Publishers, Hanover (2004)

    Google Scholar 

  52. Zolotarev, V.M.: Lévy Metric, Encyclopaedia of Mathematics. Kluwer Academic, Dordrecht (2001). M. Hazewinkel (ed.)

    Google Scholar 

  53. Bartholdi, L., Woess, W.: Spectral computations on lamplighter groups and Diestel–Leader graphs. J. Fourier Anal. Appl. 11(2), 175–202 (2005). MR 2131635 (2006e:20052)

    Article  MathSciNet  MATH  Google Scholar 

  54. Lehner, F., Neuhauser, M., Woess, W.: On the spectrum of lamplighter groups and percolation clusters. Math. Ann. 342(1), 69–89 (2008). MR 2415315 (2009d:60329)

    Article  MathSciNet  MATH  Google Scholar 

  55. Scarabotti, F., Tolli, F.: Harmonic analysis of finite lamplighter random walks. J. Dyn. Control Syst. 14(2), 251–282 (2008). MR 2390215 (2009e:43009)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, The University of British Columbia, Room 121, 1984 Mathematics Road, Vancouver, BC, Canada, V6T 1Z2

    Shankar Bhamidi

  2. Department of Statistics #3860, University of California at Berkeley, 367 Evans Hall, Berkeley, CA, 94720-3860, USA

    Steven N. Evans & Arnab Sen

Authors
  1. Shankar Bhamidi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Steven N. Evans
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Arnab Sen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Steven N. Evans.

Additional information

S.B. research supported in part by NSF Grant DMS-0704159, PIMS, and NSERC Canada.

S.N.E. supported in part by NSF grants DMS-0405778 and DMS-0907630.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Bhamidi, S., Evans, S.N. & Sen, A. Spectra of Large Random Trees. J Theor Probab 25, 613–654 (2012). https://doi.org/10.1007/s10959-011-0360-9

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10959-011-0360-9

Keywords

Mathematics Subject Classification

Search

Navigation