Asymptotic spectral analysis of growing regular graphs
HTML articles powered by AMS MathViewer
- by Akihito Hora and Nobuaki Obata PDF
- Trans. Amer. Math. Soc. 360 (2008), 899-923 Request permission
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
- Luigi Accardi, Anis Ben Ghorbal, and Nobuaki Obata, Monotone independence, comb graphs and Bose-Einstein condensation, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 7 (2004), no. 3, 419–435. MR 2085641, DOI 10.1142/S0219025704001645
- Luigi Accardi and Marek Bożejko, Interacting Fock spaces and Gaussianization of probability measures, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 1 (1998), no. 4, 663–670. MR 1665281, DOI 10.1142/S0219025798000363
- Luigi Accardi, Yukihiro Hashimoto, and Nobuaki Obata, Notions of independence related to the free group, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 1 (1998), no. 2, 201–220. MR 1628248, DOI 10.1142/S0219025798000132
- Eiichi Bannai and Tatsuro Ito, Algebraic combinatorics. I, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984. Association schemes. MR 882540
- Philippe Biane, Representations of symmetric groups and free probability, Adv. Math. 138 (1998), no. 1, 126–181. MR 1644993, DOI 10.1006/aima.1998.1745
- Norman Biggs, Algebraic graph theory, 2nd ed., Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993. MR 1271140
- Marek Bożejko, Positive-definite kernels, length functions on groups and a noncommutative von Neumann inequality, Studia Math. 95 (1989), no. 2, 107–118. MR 1038498, DOI 10.4064/sm-95-2-107-118
- T. S. Chihara, An introduction to orthogonal polynomials, Mathematics and its Applications, Vol. 13, Gordon and Breach Science Publishers, New York-London-Paris, 1978. MR 0481884
- Dragoš M. Cvetković, Michael Doob, and Horst Sachs, Spectra of graphs, Pure and Applied Mathematics, vol. 87, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1980. Theory and application. MR 572262
- S. N. Dorogovtsev and J. F. F. Mendes, Evolution of networks, Oxford University Press, Oxford, 2003. From biological nets to the Internet and WWW. MR 1993912, DOI 10.1093/acprof:oso/9780198515906.001.0001
- Gero Fendler, Central limit theorems for Coxeter systems and Artin systems of extra large type, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 6 (2003), no. 4, 537–548. MR 2030209, DOI 10.1142/S0219025703001390
- Uffe Haagerup, An example of a nonnuclear $C^{\ast }$-algebra, which has the metric approximation property, Invent. Math. 50 (1978/79), no. 3, 279–293. MR 520930, DOI 10.1007/BF01410082
- Yukihiro Hashimoto, Deformations of the semicircle law derived from random walks on free groups, Probab. Math. Statist. 18 (1998), no. 2, Acta Univ. Wratislav. No. 2111, 399–410. MR 1671628
- Yukihiro Hashimoto, Quantum decomposition in discrete groups and interacting Fock spaces, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 4 (2001), no. 2, 277–287. MR 1841622, DOI 10.1142/S0219025701000450
- Yukihiro Hashimoto, Akihito Hora, and Nobuaki Obata, Central limit theorems for large graphs: method of quantum decomposition, J. Math. Phys. 44 (2003), no. 1, 71–88. MR 1946692, DOI 10.1063/1.1528275
- Yukihiro Hashimoto, Nobuaki Obata, and Nobuyuki Tabei, A quantum aspect of asymptotic spectral analysis of large Hamming graphs, Quantum information, III (Nagoya, 2000) World Sci. Publ., River Edge, NJ, 2001, pp. 45–57. MR 1876329
- Fumio Hiai and Dénes Petz, The semicircle law, free random variables and entropy, Mathematical Surveys and Monographs, vol. 77, American Mathematical Society, Providence, RI, 2000. MR 1746976, DOI 10.1090/surv/077
- Akihito Hora, Central limit theorems and asymptotic spectral analysis on large graphs, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 1 (1998), no. 2, 221–246. MR 1628244, DOI 10.1142/S0219025798000144
- Akihito Hora, Central limit theorem for the adjacency operators on the infinite symmetric group, Comm. Math. Phys. 195 (1998), no. 2, 405–416. MR 1637801, DOI 10.1007/s002200050395
- Akihito Hora, Gibbs state on a distance-regular graph and its application to a scaling limit of the spectral distributions of discrete Laplacians, Probab. Theory Related Fields 118 (2000), no. 1, 115–130. MR 1785455, DOI 10.1007/PL00008738
- Akihito Hora, A noncommutative version of Kerov’s Gaussian limit for the Plancherel measure of the symmetric group, Asymptotic combinatorics with applications to mathematical physics (St. Petersburg, 2001) Lecture Notes in Math., vol. 1815, Springer, Berlin, 2003, pp. 77–88. MR 2009836, DOI 10.1007/3-540-44890-X_{4}
- Akihito Hora, Scaling limit for Gibbs states for Johnson graphs and resulting Meixner classes, Infin. Dimens. Anal. Quantum Probab. Relat. Top. 6 (2003), no. 1, 139–143. MR 1976874, DOI 10.1142/S0219025703001080
- Akihito Hora, Asymptotic spectral analysis on the Johnson graphs in infinite degree and zero temperature limit, The Proceedings of the Second Sendai Workshop on Quantum Probability and Quantum Information, 2004, pp. 1–10. MR 2062187, DOI 10.4036/iis.2004.1
- Akihito Hora and Nobuaki Obata, Quantum decomposition and quantum central limit theorem, Fundamental aspects of quantum physics (Tokyo, 2001) QP–PQ: Quantum Probab. White Noise Anal., vol. 17, World Sci. Publ., River Edge, NJ, 2003, pp. 284–305. MR 2003920
- Akihito Hora and Nobuaki Obata, An interacting Fock space with periodic Jacobi parameter obtained from regular graphs in large scale limit, Quantum information V, World Sci. Publ., Hackensack, NJ, 2006, pp. 121–144. MR 2210974
- A. Hora and N. Obata, Quantum Probability and Spectral Analysis of Graphs, a monograph in preparation, Springer.
- D. Igarashi and N. Obata, Asymptotic spectral analysis of growing graphs: Odd graphs and spidernets, Banach Center Publications, to appear.
- Serguei Kerov, Gaussian limit for the Plancherel measure of the symmetric group, C. R. Acad. Sci. Paris Sér. I Math. 316 (1993), no. 4, 303–308 (English, with English and French summaries). MR 1204294
- Harry Kesten, Symmetric random walks on groups, Trans. Amer. Math. Soc. 92 (1959), 336–354. MR 109367, DOI 10.1090/S0002-9947-1959-0109367-6
- Harry Kesten (ed.), Probability on discrete structures, Encyclopaedia of Mathematical Sciences, vol. 110, Springer-Verlag, Berlin, 2004. Probability Theory, 1. MR 2023649, DOI 10.1007/978-3-662-09444-0
- Brendan D. McKay, The expected eigenvalue distribution of a large regular graph, Linear Algebra Appl. 40 (1981), 203–216. MR 629617, DOI 10.1016/0024-3795(81)90150-6
- Nobuaki Obata, Quantum probabilistic approach to spectral analysis of star graphs, The Proceedings of the Second Sendai Workshop on Quantum Probability and Quantum Information, 2004, pp. 41–52. MR 2062191, DOI 10.4036/iis.2004.41
- Nobuaki Obata, Notions of independence in quantum probability theory and spectral analysis of graphs, Sūgaku 57 (2005), no. 1, 1–20 (Japanese). MR 2125194
- Naoko Saitoh and Hiroaki Yoshida, A $q$-deformed Poisson distribution based on orthogonal polynomials, J. Phys. A 33 (2000), no. 7, 1435–1444. MR 1746884, DOI 10.1088/0305-4470/33/7/311
- J. A. Shohat and J. D. Tamarkin, The Problem of Moments, American Mathematical Society Mathematical Surveys, Vol. I, American Mathematical Society, New York, 1943. MR 0008438, DOI 10.1090/surv/001
- Wolfgang Woess, Random walks on infinite graphs and groups, Cambridge Tracts in Mathematics, vol. 138, Cambridge University Press, Cambridge, 2000. MR 1743100, DOI 10.1017/CBO9780511470967
- Anatoly M. Vershik, Asymptotic combinatorics and algebraic analysis, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Zürich, 1994) Birkhäuser, Basel, 1995, pp. 1384–1394. MR 1404040
- D. V. Voiculescu, K. J. Dykema, and A. Nica, Free random variables, CRM Monograph Series, vol. 1, American Mathematical Society, Providence, RI, 1992. A noncommutative probability approach to free products with applications to random matrices, operator algebras and harmonic analysis on free groups. MR 1217253, DOI 10.1090/crmm/001
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
- 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.
- © Copyright 2007
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 2346476