Asymptotic spectral analysis of growing regular graphs

Hora, Akihito; Obata, Nobuaki

doi:10.1090/S0002-9947-07-04232-8

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