Spectra of lifted Ramanujan graphs

DOI10.1016/J.AIM.2011.03.016MaRDI QIDQ555601zbMATH OpenOpenAlexFDO

Authors Eyal Lubetzky, Benny Sudakov, Van Vu

Publication date 25 July 2011

Published in Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Ramanujan graphsrandom liftsspectral expanders

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: A random $n$-lift of a base graph $G$ is its cover graph $H$ on the vertices $[n]imesV(G)$, where for each edge $uv$ in $G$ there is an independent uniform bijection $pi$, and $H$ has all edges of the form $(i,u),(pi(i),v)$. A main motivation for studying lifts is understanding Ramanujan graphs, and namely whether typical covers of such a graph are also Ramanujan. Let $G$ be a graph with largest eigenvalue $lambd{a}_1$ and let $ho$ be the spectral radius of its universal cover. Friedman (2003) proved that every "new" eigenvalue of a random lift of $G$ is $O(h{o}^{1/2}lambd{a}_1^{1/2})$ with high probability, and conjectured a bound of $ho+o(1)$, which would be tight by results of Lubotzky and Greenberg (1995). Linial and Puder (2008) improved Friedman's bound to $O(h{o}^{2/3}lambd{a}_1^{1/3})$. For $d$-regular graphs, where $lambd{a}_1=d$ and $ho=2sqrtd-1$, this translates to a bound of $O(d^{2/3})$, compared to the conjectured $2sqrtd-1$. Here we analyze the spectrum of a random $n$-lift of a $d$-regular graph whose nontrivial eigenvalues are all at most $lambda$ in absolute value. We show that with high probability the absolute value of every nontrivial eigenvalue of the lift is $O((lambdaveeho)logho)$. This result is tight up to a logarithmic factor, and for $lambdaleq{d}^{2/3-epsilon}$ it substantially improves the above upper bounds of Friedman and of Linial and Puder. In particular, it implies that a typical $n$-lift of a Ramanujan graph is nearly Ramanujan.

Recommendations

• The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• Expansion of random graphs: new proofs, new results
• On the expansion of group-based lifts
• On the expansion of group-based lifts

Cites work

• scientific article; zbMATH DE number 3487716 (Why is no real title available?)
• scientific article; zbMATH DE number 1246230 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• scientific article; zbMATH DE number 2115090 (Why is no real title available?)
• A proof of Alon’s second eigenvalue conjecture and related problems
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Cutoff phenomena for random walks on random regular graphs
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Eigenvalues and expanders
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• Expander graphs and their applications
• Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators
• Lifts, discrepancy and nearly optimal spectral gap
• On tail probabilities for martingales
• On the second eigenvalue of a graph
• Optimal Construction of Edge-Disjoint Paths in Random Graphs
• Ramanujan graphs
• Random Lifts of Graphs: Edge Expansion
• Random graph coverings. I: General theory and graph connectivity
• Relative expanders or weakly relatively Ramanujan graphs.
• Some geometric aspects of graphs and their eigenfunctions
• The Distribution of the Largest Nontrivial Eigenvalues in Families of Random Regular Graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Word maps and spectra of random graph lifts
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators

Cited in

(26)

• On the expansion of group-based lifts
• Exposé Bourbaki 1202 : Strong convergence of the spectrum of random permutations and almost-Ramanujan graphs [after Charles Bordenave and Benoît Collins]
• The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)
• Spectrum of random d‐regular graphs up to the edge
• Cutoff for random lifts of weighted graphs
• A lower bound on the spectral radius of the universal cover of a graph
• Signatures, lifts, and eigenvalues of graphs
• Ramanujan coverings of graphs
• A new proof of Friedman's second eigenvalue theorem and its extension to random lifts
• Expansion of random graphs: new proofs, new results
• Eigenvalues of random lifts and polynomials of random permutation matrices
• Spectra and eigenspaces of arbitrary lifts of graphs
• Word maps and spectra of random graph lifts
• Interlacing families. I: Bipartite Ramanujan graphs of all degrees
• Sparse random tensors: concentration, regularization and applications
• The spectral norm of random lifts of matrices
• On the second eigenvalue of random bipartite biregular graphs
• Equitable partition for some Ramanujan graphs
• Ramanujan coverings of graphs
• On the expansion of group-based lifts
• scientific article; zbMATH DE number 7623647 (Why is no real title available?)
• The non-backtracking spectrum of the universal cover of a graph
• Functional limit theorems for random regular graphs
• Shift lifts preserving Ramanujan property
• Size biased couplings and the spectral gap for random regular graphs
• Relative expanders or weakly relatively Ramanujan graphs.

This page was built for publication: Spectra of lifted Ramanujan graphs

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