The spectrum of random lifts
arXiv:1012.4097
Abstract
For a fixed d-regular graph H, a random n-lift is obtained by replacing each vertex v of H by a "fibre" containing n vertices, then placing a uniformly random matching between fibres corresponding to adjacent vertices of H. We show that with extremely high probability, all eigenvalues of the lift that are not eigenvalues of H, have order O(sqrt(d)). In particular, if H is Ramanujan then its n-lift is with high probability nearly Ramanujan. We also show that any exceptionally large eigenvalues of the n-lift that are not eigenvalues of H, are overwhelmingly likely to have been caused by a dense subgraph of size O(|E(H)|).
35 pages; substantially revised, constants in the main results improved
Cited by in corpus (4)
- Expansion of Random Graphs: New Proofs, New Results
- Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees
- On the Relativized Alon Second Eigenvalue Conjecture I: Main Theorems, Examples, and Outline of Proof
- On the Relativized Alon Second Eigenvalue Conjecture III: Asymptotic Expansions for Tangle-Free Hashimoto Traces