Spectra of lifted Ramanujan graphs

DOI10.1016/J.AIM.2011.03.016zbMATH Open1222.05168arXiv0911.4148OpenAlexW2132266826MaRDI QIDQ555601FDOQ555601

Authors: Eyal Lubetzky, Benny Sudakov, Van Vu 

Publication date: 25 July 2011

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

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.

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

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

zbMATH Keywords

Ramanujan graphsrandom liftsspectral expanders

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (26)

• Spectrum of random d‐regular graphs up to the edge
• The spectrum of random \(k\)-lifts of large graphs (with possibly large \(k)\)
• 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
• Eigenvalues of random lifts and polynomials of random permutation matrices
• Expansion of random graphs: new proofs, new results
• 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
• On the second eigenvalue of random bipartite biregular graphs
• The spectral norm of random lifts of matrices
• Equitable partition for some Ramanujan graphs
• Ramanujan coverings of graphs
• On the expansion of group-based lifts
• Title not available (Why is that?)
• 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.
• 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]

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)