Relative expanders or weakly relatively Ramanujan graphs.
From MaRDI portal
Publication:1421136
Let \(G\) be a fixed graph with largest eigenvalue \(\lambda_0\) and with universal cover having spectral radius \(\rho\). The author demonstrates that a random cover of large degree over \(G\) has its new eigenvalues bounded in absolute value by roughly \(\sqrt{\lambda_0\, \rho}\). The main result is a ``relative version of the Broder-Shamir bound on eigenvalues of random regular graphs.
Recommendations
Cites work
- Eigenvalues and expanders
- Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
- Expanders and Diffusers
- Not every uniform tree covers Ramanujan graphs
- On the second eigenvalue and random walks in random d-regular graphs
- On the second eigenvalue of a graph
- Permutation Pseudographs and Contiguity
- Ramanujan graphs
- Random graph coverings. I: General theory and graph connectivity
- Random lifts of graphs: Independence and chromatic number
- Random lifts of graphs: perfect matchings
- Some geometric aspects of graphs and their eigenfunctions
Cited in
(48)- On codes from hypergraphs.
- Ramanujan coverings of graphs
- Poincaré inequalities and rigidity for actions on Banach spaces
- Quantum ergodicity for expanding quantum graphs in the regime of spectral delocalization
- The spectral norm of random lifts of matrices
- Cutoff for random lifts of weighted graphs
- \(L^p\)-expander graphs
- 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
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Eigenvalues of graphs and a simple proof of a theorem of Greenberg
- A random cover of a compact hyperbolic surface has relative spectral gap \(\frac{3}{16}-\varepsilon\)
- Tight products and graph expansion
- Word maps and spectra of random graph lifts
- Formal zeta function expansions and the frequency of Ramanujan graphs
- Expander graphs and their applications
- Dynamical properties of profinite actions
- Expansion of random graphs: new proofs, new results
- From Ramanujan graphs to Ramanujan complexes
- On the expansion of group-based lifts
- Spectral aspects of symmetric matrix signings
- Cutoff at the entropic time for random walks on covered expander graphs
- Signatures, lifts, and eigenvalues of graphs
- scientific article; zbMATH DE number 7268671 (Why is no real title available?)
- On the expansion of group-based lifts
- The non-backtracking spectrum of the universal cover of a graph
- Measure preserving words are primitive
- Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture: with an Appendix by Warren Dicks
- Spectra of lifted Ramanujan graphs
- Spectral gap in random bipartite biregular graphs and applications
- A note on the trace method for random regular graphs
- Near optimal spectral gaps for hyperbolic surfaces
- Spectrum of random d‐regular graphs up to the edge
- Equitable partition for some Ramanujan graphs
- Nearly optimal pseudorandomness from hardness
- Universality and sharp matrix concentration inequalities
- Strong asymptotic freeness of Haar unitaries in quasi-exponential dimensional representations
- An extension of the cogrowth formula to arbitrary subsets of the tree
- A lower bound on the spectral radius of the universal cover of a graph
- A construction of random bigraphs and their application to error correction codes
- Strongly convergent unitary representations of right-angled Artin groups
- A new approach to strong convergence
- Fractional graph expanders and network dynamics: spectral properties and diffusion with applications to quantum cryptography
- Conjugate Gradient Methods for High-Dimensional GLMMs
- Spectral statistics of the Laplacian on random covers of a closed negatively curved surface
- Spectral aspects of symmetric matrix signings
- Explicit spectral gaps for random covers of Riemann surfaces
This page was built for publication: Relative expanders or weakly relatively Ramanujan graphs.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1421136)
