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

DOI10.1080/10586458.2008.10129029zbMATH Open1151.05043arXivmath/0611649OpenAlexW2100320577MaRDI QIDQ3546266FDOQ3546266

Authors: Steven J. Miller, Tim Novikoff 

Publication date: 18 December 2008

Published in: Experimental Mathematics (Search for Journal in Brave)

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).

Full work available at URL: https://arxiv.org/abs/math/0611649

Recommendations

• Edge rigidity and universality of random regular graphs of intermediate degree
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• A proof of alon's second eigenvalue conjecture
• Ramanujan graphs

zbMATH Keywords

random graphsTracy-Widom distributionRamanujan graphslargest nontrivial eigenvalues

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52)

Cited In (27)

• Stability mapping of bipartite tight-binding graphs with losses and gain: \(\mathscr{PT}\)-symmetry and beyond
• Cycles and eigenvalues of sequentially growing random regular graphs
• Random matrix ensembles with split limiting behavior
• Spectrum of random d‐regular graphs up to the edge
• Limiting eigenvalue distribution of random matrices of Ihara zeta function of long-range percolation graphs
• The Largest Eigenvalue of Sparse Random Graphs
• Spectral gap and edge universality of dense random regular graphs
• The limiting spectral measure for ensembles of symmetric block circulant matrices
• Local Kesten-McKay law for random regular graphs
• Quantum chaos on random Cayley graphs of \(\mathrm{SL}_2 [\mathbb{Z}/ p\mathbb{Z}]\)
• The First Eigenvalue of Random Graphs
• Expansion of random graphs: new proofs, new results
• The Tracy-Widom law for some sparse random matrices
• Limiting spectral measures for random matrix ensembles with a polynomial link function
• Edge rigidity and universality of random regular graphs of intermediate degree
• Leading digit laws on linear Lie groups
• Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues
• Spectral distributions of periodic random matrix ensembles
• On Eigenvalue Distribution of Random Matrices of Ihara Zeta Function of Large Random Graphs
• Ramanujan coverings of graphs
• Spectra of lifted Ramanujan graphs
• Size biased couplings and the spectral gap for random regular graphs
• On the spectral distribution of large weighted random regular graphs
• On the distribution of eigenvalues of a simple undirected graph
• On the distribution of eigenvalues of graphs
• Spectral statistics of non-Hermitian random matrix ensembles
• Formal zeta function expansions and the frequency of Ramanujan graphs

This page was built for publication: The Distribution of the Largest Nontrivial Eigenvalues in Families of Random Regular Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3546266)