The Distribution of the Largest Non-trivial Eigenvalues in Families of Random Regular Graphs
Preprint
Abstract
Recently Friedman proved Alon's conjecture for many families of d-regular graphs, namely that given any epsilon > 0 `most' graphs have their largest non-trivial eigenvalue at most 2 sqrt{d-1}+epsilon in absolute value; if the absolute value of the largest non-trivial eigenvalue is at most 2 sqrt{d-1} then the graph is said to be Ramanujan. These graphs have important applications in communication network theory, allowing the construction of superconcentrators and nonblocking networks, coding theory and cryptography. As many of these applications depend on the size of the largest non-trivial positive and negative eigenvalues, it is natural to investigate their distributions. We show these are well-modeled by the beta=1 Tracy-Widom distribution for several families. If the observed growth rates of the mean and standard deviation as a function of the number of vertices holds in the limit, then in the limit approximately 52% of d-regular graphs from bipartite families should be Ramanujan, and about 27% from non-bipartite families (assuming the largest positive and negative eigenvalues are independent).Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Non-intersecting paths, random tilings and random matricesProbability Theory and Related Fields, 2002
- Statistical self-similarity of one-dimensional growth processesPhysica A: Statistical Mechanics and its Applications, 2000
- Existence and Explicit Constructions of q + 1 Regular Ramanujan Graphs for Every Prime Power qJournal of Combinatorial Theory, Series B, 1994
- Level-spacing distributions and the Airy kernelCommunications in Mathematical Physics, 1994
- Cubic Ramanujan graphsCombinatorica, 1992
- Eigenvalues and expandersCombinatorica, 1986
- λ1, Isoperimetric inequalities for graphs, and superconcentratorsJournal of Combinatorial Theory, Series B, 1985
- The expected eigenvalue distribution of a large regular graphLinear Algebra and its Applications, 1981
- Sur la loi limite de l'espacement des valeurs propres d'une matrice ale´atoireNuclear Physics, 1961
- On the statistical properties of the level-spacings in nuclear spectraNuclear Physics, 1960