A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
From MaRDI portal
(Redirected from 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
(67)- The spectral gap of dense random regular graphs
- Nonbacktracking spectrum of random graphs: community detection and nonregular Ramanujan graphs
- Size biased couplings and the spectral gap for random regular graphs
- Spectral gap of sparse bistochastic matrices with exchangeable rows
- Short geodesic loops and \(L^p\) norms of eigenfunctions on large genus random surfaces
- Recent progress in combinatorial random matrix theory
- The spectral gap of sparse random digraphs
- Spectra of random regular hypergraphs
- The spectral norm of random lifts of matrices
- Precise asymptotics of some meeting times arising from the voter model on large random regular graphs
- Babai's conjecture for high-rank classical groups with random generators
- A spectral condition for spectral gap: fast mixing in high-temperature Ising models
- Cutoff on graphs and the Sarnak-Xue density of eigenvalues
- Explicit expanders of every degree and size
- \(L^p\)-expander graphs
- Approximate Moore graphs are good expanders
- Recent results of quantum ergodicity on graphs and further investigation
- L^p norms and support of eigenfunctions on graphs
- Eigenvalues of random lifts and polynomials of random permutation matrices
- On the almost eigenvectors of random regular graphs
- Local Kesten-McKay law for random regular graphs
- A random cover of a compact hyperbolic surface has relative spectral gap \(\frac{3}{16}-\varepsilon\)
- Word maps and spectra of random graph lifts
- Cutoff on all Ramanujan graphs
- A proof of Alon’s second eigenvalue conjecture and related problems
- The Distribution of the Largest Nontrivial Eigenvalues in Families of Random Regular Graphs
- Expansion of random graphs: new proofs, new results
- Eigenvalues of the non-backtracking operator detached from the bulk
- 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)\)
- Spectra of lifted Ramanujan graphs
- Explicit Near-Ramanujan Graphs of Every Degree
- Spectral gap in random bipartite biregular graphs and applications
- Detection thresholds in very sparse matrix completion
- A note on the trace method for random regular graphs
- The spectral gap of random regular graphs
- The rank of sparse random matrices
- Global eigenvalue fluctuations of random biregular bipartite graphs
- Many nodal domains in random regular graphs
- Spectrum of random d‐regular graphs up to the edge
- Paradigms for Unconditional Pseudorandom Generators
- Towards optimal spectral gaps in large genus
- Strong asymptotic freeness for independent uniform variables on compact groups associated to nontrivial representations
- Spectral gap and edge universality of dense random regular graphs
- Extreme singular values of inhomogeneous sparse random rectangular matrices
- Cutoff for non-negatively curved Markov chains
- Limiting empirical spectral distribution for the non-backtracking matrix of an Erdős-Rényi random graph
- Sparse random hypergraphs: non-backtracking spectra and community detection
- The systole of random hyperbolic 3-manifolds
- Edge universality of sparse random matrices
- Delocalized eigenvectors of transitive graphs and beyond
- A note on quantum expanders
- Fluctuation of the largest eigenvalue of a kernel matrix with application in graphon-based random graphs
- On sampling from Ising models with spectral constraints
- Sparse high dimensional expanders via local lifts
- Random Schreier graphs as expanders
- The length spectrum of random hyperbolic 3-manifolds
- Tangle free permutations and the Putman-Wieland property of random covers
- Spectral gap of a convex combination of a random permutation and a deterministic matrix
- Spectral theory of isogeny graphs
- Weingarten calculus for centered random permutation matrices
- Strongly convergent unitary representations of right-angled Artin groups
- A new approach to strong convergence
- On the spectral norm of Rademacher matrices
- Limit vectors of the top k eigenvalues of d-regular graphs
- Spectral statistics of the Laplacian on random covers of a closed negatively curved surface
- Edge universality of random regular graphs of growing degrees
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)
