2009/11/21 by Eyal Lubetzky, Benny Sudakov, Lubetzky, Eyal +3
Mathematics · #05C50 #05C80 #60B20 #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #Probability (math.PR)
paper · pdf · doi:10.48550/arxiv.0911.4148
openalex publication_date 2009/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A random n-lift of a base graph G is its cover graph H on the vertices [n]× V(G), where for each edge u v in G there is an independent uniform bijection π, and H has all edges of the form (i,u),(π(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 λ1 and let ρ be the spectral radius of its universal cover. Friedman (2003) proved that every "new" eigenvalue of a random lift of G is O(ρ1/2λ11/2) with high probability, and conjectured a bound of ρ+o(1), which would be tight by results of Lubotzky and Greenberg (1995). Linial and Puder (2008) improved Friedman's bound to O(ρ2/3λ11/3). For d-regular graphs, where λ1=d and ρ=2√(d-1), this translates to a bound of O(d2/3), compared to the conjectured 2√(d-1). Here we analyze the spectrum of a random n-lift of a d-regular graph whose nontrivial eigenvalues are all at most λ in absolute value. We show that with high probability the absolute value of every nontrivial eigenvalue of the lift is O((λ\vee ρ) log ρ). This result is tight up to a logarithmic factor, and for λ≤ d2/3-ε 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.