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

DOI10.1080/10586458.2008.10129029MaRDI QIDQ3546266zbMATH OpenOpenAlexFDO

Authors Steven J. Miller, Tim Novikoff

Publication date 18 December 2008

Published in Experimental Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0611649, https://projecteuclid.org/euclid.em/1227118974

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)

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

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

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
• The limiting spectral measure for ensembles of symmetric block circulant matrices
• Spectral gap and edge universality of dense random regular graphs
• Local Kesten-McKay law for random regular graphs
• Quantum chaos on random Cayley graphs of \(\mathrm{SL}_2 [\mathbb{Z}/ p\mathbb{Z}]\)
• Expansion of random graphs: new proofs, new results
• The First Eigenvalue of Random Graphs
• The Tracy-Widom law for some sparse random matrices
• Limiting spectral measures for random matrix ensembles with a polynomial link function
• Spectral statistics of Erdős-Rényi graphs II: eigenvalue spacing and the extreme eigenvalues
• Leading digit laws on linear Lie groups
• Edge rigidity and universality of random regular graphs of intermediate degree
• 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
• On the distribution of eigenvalues of a simple undirected graph
• Size biased couplings and the spectral gap for random regular graphs
• On the distribution of eigenvalues of graphs
• On the spectral distribution of large weighted random regular 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)