Advanced search
Publication Cover
Experimental Mathematics Volume 17, 2008 - Issue 2
Submit an article Journal homepage
62
Views
28
CrossRef citations to date
0
Altmetric
Original Article

The Distribution of the Largest Nontrivial Eigenvalues in Families of Random Regular Graphs

Steven J. Miller Department of Mathematics, Williams College, Williamstown, MA 01267
,
Tim Novikoff Center for Applied Mathematics, Cornell University, 657 Frank Rhodes Hall, Ithaca, NY 14853
&
Anthony Sabelli Center for Applied Mathematics, Cornell University, 657 Frank Rhodes Hall, Ithaca, NY 14853
Pages 231-244 | Published online: 30 Jan 2011

  • Y. Alhassid. "The Statistical Theory of Quantum Dots." Rev. Mod. Phys. 72:4 (2000), 895–968.
  • N. Alon. "Eigenvalues and Expanders." Combinatorica 6:2 (1986), 83–96.
  • N. Alon and V. Milman. "λ1, Isoperimetric Inequalities for Graphs, and Superconcentrators." J. Combin. Theory Ser. B 38:1 (1985), 73–88.
  • J. Baik and E. M. Rains. Limiting distributions for a polynuclear growth model, J. Stat. Phys. 100 (2000), 523–541.
  • A. Odlyzko. "On the Distribution of Spacings between Zeros of the Zeta Function." Math. Comp. 48:177 (1987), 273–308.
  • A. Odlyzko. "The 1022-nd Zero of the Riemann Zeta Function." In Proc. Conference on Dynamical, Spectral and Arithmetic Zeta-Functions, edited by M. van Frankenhuysen and M. L. Lapidus, Amer. Math. Soc., Contemporary Math. Series. Available online (http: //www.research.att.com/~amo/doc/zeta.html), 2001. http: //www.research.att.com/~amo/doc/zeta.html
  • N. Pippenger. "Super Concentrators." SIAM Journal Comp. 6 (1977), 298–304.
  • J. Baik and E. M. Rains. "The Asymptotics of Monotone Subsequences of Involutions." Duke Math. J. 109 (2001), 205–281.
  • J. Baik and E. M. Rains. "Symmetrized Random Permutations." In Random Matrix Models and Their Applications, edited by P. Bleher and A. Its, pp. 1–19, Math. Sci. Res. Inst. Publications 40. Cambridge: Cambridge University Press, 2001.
  • J. Baik, P. Deift, and K. Johansson. "On the Distribution of the Length of the Longest Increasing Subsequence of Random Permutations." J. Amer. Math. Soc. 12 (1999), 1119–1178.
  • Yu. Baryshnikov. "GUEs and Queues." Probab. Th. Rel. Fields 119 (2001), 256–274.
  • F. Bien. "Constructions of Telephone Networks by Group Representations." Notices of the AMS 36:1 (1989), 5–22.
  • B. Bollob'as. Random Graphs. Cambridge: Cambridge University Press, 2001.
  • A. Borodin, A. Okounkov, and G. Olshanski. "Asymptotics of Plancherel Measures for Symmetric Groups." J. Amer. Math. Soc. 13 (2000), 481–515.
  • P. Chiu. "Cubic Ramanujan Graphs. Combinatorica 12:3 (1992), 275–285.
  • G. Davidoff, P. Sarnak, and A. Valette. Elementary Number Theory, Group Theory, and Ramanujan Graphs, London Mathematical Society, Student Texts 55. Cambridge: Cambridge University Press, 2003.
  • J. Dodziuk. "Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks." Trans. Amer. Math. Soc. 284:2 (1984), 787–794.
  • J. Friedman. "Some Geometric Aspects of Graphs and Their Eigenfunctions." Duke Math. J. 69:3 (1993), 487–525.
  • J. Friedman. "A Proof of Alon's Second Eigenvalue Conjecture." In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 720-724 (electronic). New York: ACM, 2003.
  • M. Gaudin. "Sur la loi limite de l'espacement des valeurs propres d'une matrice al'eatoire." Nucl. Phys. 25 (1961), 447–458.
  • O. Goldreich, R. Impagliazzo, L. Levin, R. Venkatesan, and D. Zuckerman. "Security Preserving Amplification of Hardness." In 31st Annual Symposium on Foundations of Computer Science (St. Louis, MO, 1990), Vols. I, II, pp. 318–326. Los Alamitos, CA: IEEE Comput. Soc. Press, 1990.
  • J. Gravner, C. A. Tracy, and H. Widom "Limit Theorems for Height Fluctuations in a Class of Discrete Space and Time Growth Models." J. Stat. Phys. 102 (2001), 1085–1132.
  • S. Hoory, N. Linial, and A.Wigderson "Expander Graphs and Their Applications." Bull. Amer. Math. Soc. 43 (2006), 439–561.
  • D. Jakobson, S. D. Miller, I. Rivin, and Z. Rudnick. "Eigenvalue Spacings for Regular Graphs." In Emerging Applications of Number Theory (Minneapolis, 1996), pp. 317–327, IMA Volumes in Mathematics and Its Applications 109. New York: Springer, 1999.
  • K. Johansson. "Discrete Orthogonal Polynomial Ensembles and the Plancherel Measure." Ann. Math. 153 (2001), 259–296.
  • K. Johansson. "Non-intersecting Paths, Random Tilings and Random Matrices." Probab. Th. Rel. Fields 123 (2002), 225–280.
  • K. Johansson. Toeplitz determinants, random growth and determinantal processes, ICM Vol. III (2002), 53–62.
  • J. P. Keating and N. C. Snaith. "Random Matrix Theory and ζ(1/2 + it)." Comm. Math. Phys. 214:1 (2000), 57–89.
  • A. Lubotzky, R. Phillips, and P. Sarnak. "Ramanujan Graphs." Combinatorica 8:3 (1988), 261–277.
  • G. A. Margulis. "Explicit Group-Theoretic Constructions of Combinatorial Schemes and Their Applications in the Construction of Expanders and Concentrators" (Russian). Problemy Peredachi Informatsii 24:1 (1988), 51–60; translation in Problems Inform. Transmission 24:1 (1988), 39–46.
  • B. McKay. "The Expected Eigenvalue Distribution of a Large Regular Graph." Linear Algebra Appl. 40 (1981), 203–216.
  • M. Mehta. "On the Statistical Properties of Level Spacings in Nuclear Spectra." Nucl. Phys. 18 (1960), 395-419.
  • M. Mehta. Random Matrices, 2nd edition. Boston: Academic Press, 1991.
  • M. Morgenstern. "Existence and Explicit Constructions of q +1 Regular Ramanujan Graphs for Every Prime Power q." J. Combin. Theory Ser. B 62:1 (1994), 44–62.
  • M. Ram Murty "Ramanujan Graphs." J. Ramanujan Math. Soc. 18:1 (2003), 33–52.
  • M. Prähofer and H. Spohn. "Statistical Self-Similarity of One-Dimensional Growth Processes." Physica A 279 (2000), 342–352.
  • M. Prähofer and H. Spohn. "Universal Distributions for Growth Processes in 1 + 1 Dimensions and Random Matrices." Phys. Rev. Lett. 84 (2000), 4882–4885.
  • P. Sarnak. Some Applications of Modular Forms, Cambridge Trusts in Mathematics, 99, Cambridge: Cambridge University Press, 1990.
  • P. Sarnak. "What Is an Expander?" Notices of the AMS 51:7 (2004), 762–763.
  • A. Soshnikov. "A Note on Universality of the Distribution of the Largest Eigenvalue in Certain Classes of Sample Covariance Matrices. Preprint, arXiv: math.PR/0104113, 2008.
  • M. Sipser and Spielman "Expander Codes." IEEE Trans. Inform. Theory 42:6 (1996), 1710–1722.
  • C. A. Tracy and H. Widom. "Level-Spacing Distributions and the Airy Kernel." Comm. Math. Phys. 159 (1994), 151–174.
  • C. Tracy and H. Widom. "On Orthogonal and Sympletic Matrix Ensembles. Communications in Mathematical Physics 177 (1996), 727–754.
  • C. Tracy and H. Widom. "Distribution Functions for Largest Eigenvalues and Their Applications." ICM Vol. I (2002), 587–596.
  • M. G. Vavilov, P. W. Brouwer, V. Ambegaokar, and C. W. J. Beenakker. "Universal Gap Fluctuations in the Superconductor Proximity Effect." Phys. Rev. Lett. 86 (2001), 874–877.
  • E. Wigner. "Statistical Properties of Real Symmetric Matrices." In Canadian Mathematical Congress Proceedings, pp. 174–184. Toronto: University of Toronto Press, 1957.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.