6 Spectrum and expansion in lifts of graphs
\(f:V(H)\to V(G)\) is a covering map if it maps each \(\Gamma _H(v)\) bijectively onto \(\Gamma _G(f(v))\); then \(H\) is a lift of \(G\).
For connected \(G\), all vertex/edge fibers \(f^{-1}(\cdot )\) have a common size \(n\); such \(H\) is an \(n\)-lift.
\(\mathcal L_n(G)\): \(V(H)=V(G)\times [n]\), and each edge \(e\in E(G)\) carries a permutation \(\pi _e\in S_n\), with fiber edges \(((u,i),(v,\pi _e(i)))\).
If \(h\) is an eigenfunction of \(G\) with eigenvalue \(\lambda \) then \(h\circ f\) is one of \(H\) (an old eigenvalue); the remaining eigenvalues of \(H\) are new.
A new eigenfunction \(\psi \) satisfies \(\sum _{f(x)=v}\psi (x)=0\) for every \(v\).
\(\psi \) is orthogonal to all old eigenfunctions \(h\circ f\), so \(\sum _vh(v)\sum _{f(x)=v}\psi (x)=0\) for every eigenfunction \(h\) of \(G\); since the \(h\) span all functions on \(V(G)\), the fiber sums vanish.
A signing \(\tilde A\) of \(A_G\) replaces some \(1\)-entries by \(-1\) (symmetrically); signings correspond bijectively to \(2\)-lifts.
The new eigenvalues of the \(2\)-lift encoded by \(\tilde A\) are exactly the eigenvalues of \(\tilde A\).
The map \(\psi (v,1)=-\psi (v,2)=\phi (v)\) is a bijection between eigenfunctions \(\phi \) of \(\tilde A\) and new eigenfunctions of the lift, preserving eigenvalues.
\(\hat G\) is the infinite tree of non-backtracking walks from a fixed vertex; every connected lift of \(G\) is a quotient of \(\hat G\).
\(\rho (H)=\sup \{ |\lambda |:\lambda \in \mathrm{spec}(H)\} \).
If a family \(\{ G_i\} \) shares universal cover \(T\) then \(\lambda (G_i)\ge \rho (T)-o(1)\).
As in Proof I of Alon–Boppana, using \(f=\pm 1\) on two far vertices: closed walks of length \(2k\) in \(T\) number \(\ge (\rho -o(1))^{2k}\), bounding the Rayleigh quotient of \(A^{2k}\).
\(G\) is Ramanujan if \(\lambda (G)\le \rho (\hat G)\) (coincides with the regular definition when \(\hat G=\mathbf{T}_d\)).
Every \(d\)-regular (Ramanujan) graph has a \(2\)-lift all of whose new eigenvalues lie in \([-2\sqrt{d-1},2\sqrt{d-1}]\).
Every \(d\)-regular adjacency matrix has a signing \(\tilde A\) with \(x\tilde Ax\le O(\sqrt d\log d\, \| x\| ^2)\) for all \(x\in \{ -1,0,1\} ^V\).
For every \(d\ge 3\) there is a mildly explicit family of \((n,d,\alpha )\)-graphs with \(\alpha d=O(\sqrt{d\log ^3d})\).