A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
From MaRDI portal
Publication:3389206
Abstract: It was conjectured by Alon and proved by Friedman that a random -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 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 -lifts of graphs and improve a recent result by Friedman and Kohler.
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
Cited in
(48)- A spectral condition for spectral gap: fast mixing in high-temperature Ising models
- The spectral gap of random regular graphs
- The rank of sparse random matrices
- 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
- The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)
- Spectrum of random d‐regular graphs up to the edge
- Cutoff at the entropic time for random walks on covered expander graphs
- 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
- Local Kesten-McKay law for random regular graphs
- Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
- Spectral gap in random bipartite biregular graphs and applications
- Expansion of random graphs: new proofs, new results
- Eigenvalues of random lifts and polynomials of random permutation matrices
- 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
- Short geodesic loops and \(L^p\) norms of eigenfunctions on large genus random surfaces
- A note on the trace method for random regular graphs
- Spectra of random regular hypergraphs
- Eigenvalues of the non-backtracking operator detached from the bulk
- Recent progress in combinatorial random matrix theory
- Recent results of quantum ergodicity on graphs and further investigation
- Global eigenvalue fluctuations of random biregular bipartite graphs
- 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 on graphs and the Sarnak-Xue density of eigenvalues
- On the almost eigenvectors of random regular graphs
- Cutoff for non-negatively curved Markov chains
- L^p norms and support of eigenfunctions on graphs
- Explicit Near-Ramanujan Graphs of Every Degree
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)
