Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Asymptotic spectral analysis of growing regular graphs


Authors: Akihito Hora and Nobuaki Obata
Journal: Trans. Amer. Math. Soc. 360 (2008), 899-923
MSC (2000): Primary 46L53; Secondary 05C50, 42C05, 60F05, 81S25
DOI: https://doi.org/10.1090/S0002-9947-07-04232-8
Published electronically: August 29, 2007
MathSciNet review: 2346476
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We propose the quantum probabilistic techniques to obtain the asymptotic spectral distribution of the adjacency matrix of a growing regular graph. We prove the quantum central limit theorem for the adjacency matrix of a growing regular graph in the vacuum and deformed vacuum states. The condition for the growth is described in terms of simple statistics arising from the stratification of the graph. The asymptotic spectral distribution of the adjacency matrix is obtained from the classical reduction.


References [Enhancements On Off] (What's this?)

  • 1. L. Accardi, A. Ben Ghorbal and N. Obata, Monotone independence, comb graphs and Bose-Einstein condensation, Infin. Dimen. Anal. Quantum Probab. Relat. Top. 7 (2004), 419-435. MR 2085641 (2005f:81123)
  • 2. L. Accardi and M. Bozejko, Interacting Fock spaces and Gaussianization of probability measures, Infin. Dimen. Anal. Quantum Probab. Relat. Top. 1 (1998), 663-670. MR 1665281 (2000d:60158)
  • 3. L. Accardi, Y. Hashimoto and N. Obata, Notions of independence related to the free group, Infin. Dimen. Anal. Quantum Probab. Relat. Top. 1 (1998), 201-220. MR 1628248 (99g:46087)
  • 4. E. Bannai and T. Ito, Algebraic Combinatorics I, Association Schemes, Benjamin, 1984. MR 882540 (87m:05001)
  • 5. P. Biane, Representations of symmetric groups and free probability, Adv. Math. 138 (1998), 126-181. MR 1644993 (2001b:05225)
  • 6. N. Biggs, Algebraic Graph Theory (2nd Ed.), Cambridge University Press, 1993. MR 1271140 (95h:05105)
  • 7. M. Bozejko, Positive-definite kernels, length functions on groups and a noncommutative von Neumann inequality, Studia Math. XCV (1989), 107-118. MR 1038498 (91f:43011)
  • 8. T. S. Chihara, An Introduction to Orthogonal Polynomials, Gordon and Breach, 1978. MR 0481884 (58:1979)
  • 9. D. M. Cvetkovic, M. Doob and H. Sachs, Spectra of Graphs, Academic Press, 1979. MR 572262 (81i:05054)
  • 10. S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks, Oxford University Press, 2003. MR 1993912 (2005d:05002)
  • 11. G. Fendler, Central limit theorems for Coxeter systems and Artin systems of extra large type, Infin. Dimen. Anal. Quantum Probab. Relat. Top. 6 (2003), 537-548. MR 2030209 (2004i:46096)
  • 12. U. Haagerup, An example of a nonnuclear C$ ^*$-algebra which has the metric approximation property, Invent. Math. 50 (1979), 279-293. MR 520930 (80j:46094)
  • 13. Y. Hashimoto, Deformations of the semicircle law derived from random walks on free groups, Prob. Math. Stat. 18 (1998), 399-410. MR 1671628 (2000f:60012)
  • 14. Y. Hashimoto, Quantum decomposition in discrete groups and interacting Fock spaces, Infin. Dimen. Anal. Quantum Probab. Relat. Top. 4 (2001), 277-287. MR 1841622 (2003c:81102)
  • 15. Y. Hashimoto, A. Hora and N. Obata, Central limit theorems for large graphs: Method of quantum decomposition, J. Math. Phys. 44 (2003), 71-88. MR 1946692 (2004f:81120)
  • 16. Y. Hashimoto, N. Obata and N. Tabei, A quantum aspect of asymptotic spectral analysis of large Hamming graphs, Quantum Information III (T. Hida and K. Saitô, Eds.), World Scientific, 2001, pp. 45-57. MR 1876329
  • 17. F. Hiai and D. Petz, The Semicircle Law, Free Random Variables and Entropy, Amer. Math. Soc., 2000. MR 1746976 (2001j:46099)
  • 18. A. Hora, Central limit theorems and asymptotic spectral analysis on large graphs, Infin. Dimen. Anal. Quantum Probab. Relat. Top. 1 (1998), 221-246. MR 1628244 (99g:46089)
  • 19. A. Hora, Central limit theorem for the adjacency operators on the infinite symmetric group, Commun. Math. Phys. 195 (1998), 405-416. MR 1637801 (99i:46058)
  • 20. A. Hora, Gibbs state on a distance-regular graph and its application to a scaling limit of the spectral distributions of discrete Laplacians, Probab. Theory Relat. Fields 118 (2000), 115-130. MR 1785455 (2002c:05163)
  • 21. A. Hora, A noncommutative version of Kerov's Gaussian limit for the Plancherel measure of the symmetric group, Asymptotic Combinatorics with Applications to Mathematical Physics (A. M. Vershik, Ed.), Lect. Notes in Math. Vol. 1815, Springer, 2003, pp. 77-88. MR 2009836 (2004k:60056)
  • 22. A. Hora, Scaling limit for Gibbs states for Johnson graphs and resulting Meixner classes, Infin. Dimen. Anal. Quantum Probab. Relat. Top. 6 (2003), 139-143. MR 1976874 (2004k:60057)
  • 23. A. Hora, Asymptotic spectral analysis on the Johnson graphs in infinite degree and zero temperature limit, Interdiscip. Inform. Sci. 10 (2004), 1-10. MR 2062187 (2005i:82032)
  • 24. A. Hora and N. Obata, Quantum decomposition and quantum central limit theorem, Fundamental Problems in Quantum Physics (L. Accardi and S. Tasaki, Eds.), World Scientific, 2003, pp. 284-305. MR 2003920 (2004i:81131)
  • 25. A. Hora and N. Obata, An interacting Fock space with periodic Jacobi parameter obtained from regular graphs in large scale limit, Quantum Information V (T. Hida and K. Saitô, Eds.), World Scientific, 2005, to appear. MR 2210974
  • 26. A. Hora and N. Obata, Quantum Probability and Spectral Analysis of Graphs, a monograph in preparation, Springer.
  • 27. D. Igarashi and N. Obata, Asymptotic spectral analysis of growing graphs: Odd graphs and spidernets, Banach Center Publications, to appear.
  • 28. S. Kerov, Gaussian limit for the Plancherel measure of the symmetric group, C. R. Acad. Sci. Paris 316 Série I (1993), 303-308. MR 1204294 (93k:20106)
  • 29. H. Kesten, Symmetric random walks on groups, Trans. Amer. Math. Soc. 92 (1959), 336-354. MR 0109367 (22:253)
  • 30. H. Kesten (Ed.), Probability on Discrete Structures, Encyclopaedia of Mathematical Sciences, Vol. 110, Springer, 2004. MR 2023649 (2004g:60003)
  • 31. B. D. McKay, The expected eigenvalue distribution of a large regular graph, Linear Alg. Appl. 40 (1981), 203-216. MR 629617 (84h:05089)
  • 32. N. Obata, Quantum probabilistic approach to spectral analysis of star graphs, Interdiscip. Inform. Sci. 10 (2004), 41-52. MR 2062191 (2005a:05140)
  • 33. N. Obata, Notions of independence in quantum probability theory and spectral analysis of graphs, Sugaku Expositions 57 (2005), 1-20. MR 2125194 (2006f:46059)
  • 34. N. Saitoh and H. Yoshida, A $ q$-deformed Poisson distribution based on orthogonal polynomials, J. Phys. A: Math. Gen. 33 (2000), 1435-1444. MR 1746884 (2001c:33034)
  • 35. J. A. Shohat and J. D. Tamarkin, The Problem of Moments, Amer. Math. Soc., 1943. MR 0008438 (5:5c)
  • 36. W. Woess, Random Walks on Infinite Graphs and Groups, Cambridge University Press, 2000. MR 1743100 (2001k:60006)
  • 37. A. M. Vershik, Asymptotic combinatorics and algebraic analysis, Proc. International Congress of Mathematicians, Vol. 2 (Zürich, 1994), Birkhäuser, Basel, 1995, pp. 1384-1394. MR 1404040 (98e:60018)
  • 38. D. Voiculescu, K. Dykema and A. Nica, Free Random Variables, CRM Monograph Series, Amer. Math. Soc., 1992. MR 1217253 (94c:46133)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 46L53, 05C50, 42C05, 60F05, 81S25

Retrieve articles in all journals with MSC (2000): 46L53, 05C50, 42C05, 60F05, 81S25


Additional Information

Akihito Hora
Affiliation: Graduate School of Natural Science and Technology, Okayama University, Okayama, 700-8530 Japan
Address at time of publication: Graduate School of Mathematics, Nagoya University, Nagoya, 464-8602 Japan
Email: hora@ems.okayama-u.ac.jp, hora@math.nagoya-u.ac.jp

Nobuaki Obata
Affiliation: Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579 Japan
Email: obata@math.is.tohoku.ac.jp

DOI: https://doi.org/10.1090/S0002-9947-07-04232-8
Keywords: Adjacency matrix, interacting Fock space, orthogonal polynomial, quantum central limit theorem, quantum decomposition, spectral distribution
Received by editor(s): October 17, 2005
Received by editor(s) in revised form: November 5, 2005
Published electronically: August 29, 2007
Additional Notes: This work was supported in part by JSPS Grant-in-Aid for Scientific Research No. 15340039.
Article copyright: © Copyright 2007 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society