The Relativized Second Eigenvalue Conjecture of Alon

Abstract

We prove a relativization of the Alon Second Eigenvalue Conjecture for all $d$-regular base graphs, $B$, with $d\ge 3$: for any $\epsilon >0$, we show that a random covering map of degree $n$ to $B$ has a new eigenvalue greater than $2\sqrt{d-1}+\epsilon$ in absolute value with probability $O(1/n)$. Furthermore, if $B$ is a Ramanujan graph, we show that this probability is proportional to $n^{-{\eta }_{\mathrm{fund}}(B)}$, where ${\eta }_{\mathrm{fund}}(B)$ is an integer depending on $B$, which can be computed by a finite algorithm for any fixed $B$. For any $d$-regular graph, $B$, ${\eta }_{\mathrm{fund}}(B)$ is greater than $\sqrt{d-1}$. Our proof introduces a number of ideas that simplify and strengthen the methods of Friedman's proof of the original conjecture of Alon. The most significant new idea is that of a ``certified trace,'' which is not only greatly simplifies our trace methods, but is the reason we can obtain the $n^{-{\eta }_{\mathrm{fund}}(B)}$ estimate above. This estimate represents an improvement over Friedman's results of the original Alon conjecture for random $d$-regular graphs, for certain values of $d$.

References in corpus (2)

• Sheaves on Graphs, Their Homological Invariants, and a Proof of the Hanna Neumann Conjecture
• Sheaves on Graphs and Their Homological Invariants

Cited by in corpus (6)

• Expansion of Random Graphs: New Proofs, New Results
• ${\ell }_p$-Spread and Restricted Isometry Properties of Sparse Random Matrices
• Ramanujan Graphs and Digraphs
• Spectrum of Random $d$-regular Graphs Up to the Edge
• A Note on the Trace Method for Random Regular Graphs
• Norm of matrix-valued polynomials in random unitaries and permutations