A new proof of Friedman's second eigenvalue theorem and its extension to random lifts

DOI10.24033/ASENS.2450zbMATH Open1462.05324arXiv1502.04482OpenAlexW1722290085MaRDI QIDQ3389206FDOQ3389206

Authors: Charles Bordenave 

Publication date: 10 May 2021

Published in: Annales Scientifiques de l?tcole Normale Sup�rieure (Search for Journal in Brave)

Abstract: It was conjectured by Alon and proved by Friedman that a random $d$-regular graph has nearly the largest possible spectral gap, more precisely, the largest absolute value of the non-trivial eigenvalues of its adjacency matrix is at most $2sqrtd-1+o(1)$ with probability tending to one as the size of the graph tends to infinity. We give a new proof of this statement. We also study related questions on random $n$-lifts of graphs and improve a recent result by Friedman and Kohler.

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

Recommendations

• Spectra of lifted Ramanujan graphs
• A proof of Alon’s second eigenvalue conjecture and related problems
• Expansion of random graphs: new proofs, new results
• The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)
• On the second eigenvalue and random walks in random \(d\)-regular graphs

zbMATH Keywords

spectral gaprandom regular graphsrandom lift

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Random matrices (probabilistic aspects) (60B20) Graph theory (including graph drawing) in computer science (68R10)

Cited In (48)

• A spectral condition for spectral gap: fast mixing in high-temperature Ising models
• A proof of Alon’s second eigenvalue conjecture and related problems
• The spectral gap of sparse random digraphs
• Explicit expanders of every degree and size
• Babai's conjecture for high-rank classical groups with random generators
• Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
• A random cover of a compact hyperbolic surface has relative spectral gap \(\frac{3}{16}-\varepsilon\)
• Strong asymptotic freeness for independent uniform variables on compact groups associated to nontrivial representations
• The spectral gap of dense random regular graphs
• Spectrum of random d‐regular graphs up to the edge
• Cutoff at the entropic time for random walks on covered expander graphs
• The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)
• Paradigms for Unconditional Pseudorandom Generators
• Towards optimal spectral gaps in large genus
• Spectral gap and edge universality of dense random regular graphs
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
• Local Kesten-McKay law for random regular graphs
• Spectral gap in random bipartite biregular graphs and applications
• Eigenvalues of random lifts and polynomials of random permutation matrices
• Expansion of random graphs: new proofs, new results
• Spectral gap of sparse bistochastic matrices with exchangeable rows
• Word maps and spectra of random graph lifts
• \(L^p\)-expander graphs
• Approximate Moore graphs are good expanders
• A note on the trace method for random regular graphs
• Short geodesic loops and \(L^p\) norms of eigenfunctions on large genus random surfaces
• Eigenvalues of the non-backtracking operator detached from the bulk
• Spectra of random regular hypergraphs
• Recent progress in combinatorial random matrix theory
• Global eigenvalue fluctuations of random biregular bipartite graphs
• Recent results of quantum ergodicity on graphs and further investigation
• The spectral norm of random lifts of matrices
• Cutoff on all Ramanujan graphs
• The Distribution of the Largest Nontrivial Eigenvalues in Families of Random Regular Graphs
• Precise asymptotics of some meeting times arising from the voter model on large random regular graphs
• Many nodal domains in random regular graphs
• Sparse random hypergraphs: non-backtracking spectra and community detection
• Spectra of lifted Ramanujan graphs
• Size biased couplings and the spectral gap for random regular graphs
• Detection thresholds in very sparse matrix completion
• Cutoff for non-negatively curved Markov chains
• On the almost eigenvectors of random regular graphs
• Cutoff on graphs and the Sarnak-Xue density of eigenvalues
• Explicit Near-Ramanujan Graphs of Every Degree
• \(L^p\) norms and support of eigenfunctions on graphs
• The spectral gap of random regular graphs
• The rank of sparse random matrices

This page was built for publication: A new proof of Friedman's second eigenvalue theorem and its extension to random lifts

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