  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_{\rm \,fund}}(B)}$, where ${\eta_{\rm \,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_{\rm \,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_{\rm \,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$.
